Abstract
The parameterized complexity of a problem is generally considered “settled” once it has been shown to lie in FPT or to be complete for a class in the W-hierarchy or a similar parameterized hierarchy. Several natural parameterized problems have, however, resisted such a classification. At least in some cases, the reason is that upper and lower bounds for their parameterized space complexity have recently been obtained that rule out completeness results for parameterized time classes. In this paper, we make progress in this direction by proving that the associative generability problem and the longest common subsequence problem are complete for parameterized space classes. These classes are defined in terms of different forms of bounded nondeterminism and in terms of simultaneous time–space bounds. As a technical tool we introduce a “union operation” that translates between problems complete for classical complexity classes and for W-classes.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Annals of Pure and Applied Logic 84(1), 119–138 (1997)
Elberfeld, M., Stockhusen, C., Tantau, T.: On the Space Complexity of Parameterized Problems. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 206–217. Springer, Heidelberg (2012)
Guillemot, S.: Parameterized complexity and approximability of the longest compatible sequence problem. Discrete Optimization 8(1), 50–60 (2011)
Flum, J., Grohe, M.: Describing parameterized complexity classes. Information and Computation 187, 291–319 (2003)
Stockhusen, C., Tantau, T.: Completeness results for parameterized space classes. Technical Report arXiv:1308.2892, ArXiv e-prints (2013)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)
Chen, Y., Flum, J., Grohe, M.: Bounded nondeterminism and alternation in parameterized complexity theory. In: Proceedings of the 18th IEEE Annual Conference on Computational Complexity, CCC 2003, pp. 13–29 (2003)
Kintala, C.M.R., Fischer, P.C.: Refining nondeterminism in relativized polynomial-time bounded computations. SIAM Journal on Computing 1(9), 46–53 (1980)
Buss, J., Goldsmith, J.: Nondeterminism within P. SIAM Journal on Computing, 560–572 (1993)
Buss, S.R.: The Boolean formula value problem is in ALOGTIME. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 123–131. ACM (1987)
Buss, S., Cook, S., Gupta, A., Ramachandran, V.: An optimal parallel algorithm for formula evaluation. SIAM Journal on Computing 21(4), 755–780 (1992)
Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. Theoretical Computer Science 3(1), 105–117 (1976)
Jones, N.D., Lien, Y.E., Laaser, W.T.: New problems complete for nondeterministic log space. Mathematical Systems Theory 10(1), 1–17 (1976)
Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: On the parameterized complexity of short computation and factorization. Archive for Mathematical Logic 36(4-5), 321–337 (1997)
Hartmanis, J.: On non-determinancy in simple computing devices. Acta Informatica 1, 336–344 (1972)
Fellows, M., Hallett, M., Stege, U.: Analogs & duals of the MAST problem for squences & trees. Journal of Algorithms 49(1), 192–216 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Stockhusen, C., Tantau, T. (2013). Completeness Results for Parameterized Space Classes. In: Gutin, G., Szeider, S. (eds) Parameterized and Exact Computation. IPEC 2013. Lecture Notes in Computer Science, vol 8246. Springer, Cham. https://doi.org/10.1007/978-3-319-03898-8_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-03898-8_28
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03897-1
Online ISBN: 978-3-319-03898-8
eBook Packages: Computer ScienceComputer Science (R0)