×

zbMATH — the first resource for mathematics

Describing parameterized complexity classes. (English) Zbl 1076.68031
Summary: We describe parameterized complexity classes by means of classical complexity theory and descriptive complexity theory. For every classical complexity class we introduce a parameterized analogue in a natural way. In particular, the analogue of polynomial time is the class of all fixed-parameter tractable problems. We develop a basic complexity theory for the parameterized analogues of classical complexity classes and give, among other things, complete problems and logical descriptions. We then show that most of the well-known intractable parameterized complexity classes are not analogues of classical classes. Nevertheless, for all these classes we can provide natural logical descriptions.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q19 Descriptive complexity and finite models
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abrahamson, K.A.; Downey, R.G.; Fellows, M.R., Fixed-parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogs, Ann. pure appl. logic, 73, 235-276, (1995) · Zbl 0828.68077
[2] M. Alekhnovich, A. Razborov, Resolution is not automatizable unless W[P] is tractable, in: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 210-219 · Zbl 1169.03044
[3] Bodlaender, H.L.; Downey, R.G.; Fellows, M.R.; Hallett, M.T.; Wareham, H.T., Parameterized complexity analysis in computational biology, Comput. appl. biosci., 11, 49-57, (1995)
[4] Büchi, J.R., Weak second-order arithmetic and finite automata, Zeitschrift für mathematische logik und grundlagen der Mathematik, 6, 66-92, (1960) · Zbl 0103.24705
[5] Cai, L.; Chen, J.; Downey, R.G.; Fellows, M.R., Advice classes of parameterized tractability, Ann. pure appl. logic, 84, 119-138, (1997) · Zbl 0873.68071
[6] Y. Chen, J. Flum, Machine characterizations of the classes of the W-hierarchy, in: Proceedings of the 17th International Workshop on Computer Science Logic, Lecture Notes in Computer Science, Springer-Verlag, 2003, to appear · Zbl 1116.68470
[7] Y. Chen, J. Flum, M. Grohe, Bounded nondeterminism and alternation in parameterized complexity theory, in: Proceedings of the 18th IEEE Conference on Computational Complexity, pp. 13-29, 2003
[8] Downey, R.G.; Fellows, M.R., Fixed-parameter tractability and completeness I: basic results, SIAM J. comput., 24, 873-921, (1995) · Zbl 0830.68063
[9] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer Berlin · Zbl 0914.68076
[10] Downey, R.G.; Fellows, M.R.; Regan, K., Descriptive complexity and the W-hierarchy, (), 119-134 · Zbl 0897.03029
[11] Downey, R.G.; Fellows, M.R.; Taylor, K., The parameterized complexity of relational database queries and an improved characterization of W[1], (), 194-213 · Zbl 0918.68018
[12] Ebbinghaus, H.-D.; Flum, J., Finite model theory, (1999), Springer Berlin
[13] Ebbinghaus, H.-D.; Flum, J.; Thomas, W., Mathematical logic, (1994), Springer Berlin · Zbl 0795.03001
[14] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, (), 43-73
[15] Flum, J.; Grohe, M., Fixed-parameter tractability, definability, and model checking, SIAM J. comput., 31, 1, 113-145, (2001) · Zbl 0992.68060
[16] Gaifman, H., On local and non-local properties, (), 105-135
[17] Gottlob, G.; Leone, N.; Sideri, M., Fixed-parameter complexity in AI and nonmonotonic reasoning, (), 1-18 · Zbl 0955.68057
[18] Grohe, M., Generalized model-checking problems for first-order logic, (), 12-26 · Zbl 0976.68077
[19] M. Grohe, The parameterized complexity of database queries, in: Proceedings of the 20th ACM Symposium on Principles of Database Systems, 2001, pp. 82-92
[20] M. Grohe, T. Schwentick, L. Segoufin, When is the evaluation of conjunctive queries tractable, in: Proceedings of the 33rd ACM Symposium on Theory of Computing, 2001, pp. 657-666 · Zbl 1323.68251
[21] Immerman, N., Relational queries computable in polynomial time, Inform. control, 68, 86-104, (1986) · Zbl 0612.68086
[22] Immerman, N., Languages that capture complexity classes, SIAM J. comput., 16, 760-778, (1987) · Zbl 0634.68034
[23] Immerman, N., Descriptive complexity, (1999), Springer Berlin · Zbl 0918.68031
[24] C.H. Papadimitriou, M. Yannakakis, On the complexity of database queries, in: Proceedings of the 17th ACM Symposium on Principles of Database Systems, 1997, pp. 12-19
[25] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley · Zbl 0557.68033
[26] U. Stege, Resolving conflicts in problems from computational biology. PhD thesis, ETH Zuerich, 2000. PhD thesis No.13364
[27] L.J. Stockmeyer, The complexity of decision problems in automata theory. PhD thesis, Department of Electrical Engineering, MIT, 1974
[28] M.Y. Vardi, The complexity of relational query languages, in: Proceedings of the 14th ACM Symposium on Theory of Computing, 1982, pp. 137-146
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.