Abstract
We study the parameterized space complexity of model-checking first-order logic with a bounded number of variables. By restricting the number of the quantifier alternations we obtain problems complete for a natural hierarchy between parameterized logarithmic space and FPT. We call this hierarchy the tree hierarchy, provide a machine characterization, and link it to the recently introduced classes PATH and TREE. We show that the lowest class PATH collapses to parameterized logarithmic space only if Savitch’s theorem can be improved. Finally, we settle the complexity with respect to the tree-hierarchy of finding short undirected paths and small undirected trees.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. of Comp. and Syst. Sciences 75(8), 423–434 (2009)
Borodin, A., Cook, S.A., Dymond, P.W., Ruzzo, W.L., Tompa, M.: Two applications of inductive counting for complementation problems. SIAM J. on Computing 18(3), 559–578 (1989)
Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: On the structure of parameterized problems in NP. Information and Computation 123, 38–49 (1995)
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)
Chen, H., Müller, M.: The fine classification of conjunctive queries and parameterized logarithmic space complexity. In: Proc. of PODS 2013, pp. 309–320 (2013); full version arXiv:1306.5424 [cs.CC]
Chen, J., Kneis, J., Lu, S., Mölle, D., Richter, S., Rossmanith, P., Sze, S.-H., Zhang, F.: Randomized divide-and-conquer: Improved path, matching, and packing algorithms. SIAM J. on Computing 38(6), 2526–2547 (2009)
Chen, Y., Flum, J.: On parameterized path and chordless path problems. In: Proc. of CCC 2007, pp. 250–263 (2007)
Chen, Y., Flum, J.: On optimal inverters. Bull. Symb. Logic (to appear, 2014)
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)
Flum, J., Grohe, M.: Describing parameterized complexity classes. Information and Computation 187(2), 291–319 (2003)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)
M. Frick and M. Grohe. Deciding first-order properties of locally tree-decomposable structures. J. of the ACM, 48(6):1184–1206, 2001.
Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. of the ACM 54(1), 1:1–1:24 (2007)
Grohe, M., Kreutzer, S.: Methods for algorithmic meta theorems. In: Model Theoretic Meth. in Finite Combinatorics, Cont. Math., vol. 558, pp. 181–206. AMS (2011)
Grohe, M., Schwentick, T., Segoufin, L.: When is the evaluation of conjunctive queries tractable? In: Proc. of STOC 2001 (2001)
Hemaspaandra, L.A., Ogihara, M., Toda, S.: Space-efficient recognition of sparse self-reducible languages. Computational Complexity 4, 262–296 (1994)
Levin, L.: Universal sequential search problems. Problems of Information Transmission 9(3), 265–266 (1973)
Lipton, J.R.: The P = NP Question and Gödel’s Lost Letter. Springer (2010)
Montoya, J.-A., Müller, M.: Parameterized random complexity. Theory of Computing Systems 52(2), 221–270 (2013)
Potechin, A.: Bounds on monotone switching networks for directed connectivity. In: Proc. of FOCS 2010, pp. 553–562 (2010)
Reingold, O.: Undirected connectivity in log-space. J. of the ACM 55(4) (2008)
Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. of Comp. and Syst. Sciences 4(2), 177–192 (1970)
Schweikardt, N., Schwentick, T., Segoufin, L.: Database theory: Query languages. In: Algorithms and Theory of Computation, pp. 19.1–19.34. Chapman & Hall/CRC (2010)
Vardi, M.Y.: On the complexity of bounded-variable queries. In: Proc. of PODS 1995, pp. 266–276. ACM Press (1995)
Venkateswaran, H.: Properties that characterize LOGCFL. J. of Comp. and Syst. Sciences 43(2), 380–404 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag GmbH Berlin Heidelberg
About this paper
Cite this paper
Chen, Y., Müller, M. (2014). Bounded Variable Logic, Parameterized Logarithmic Space, and Savitch’s Theorem. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds) Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, vol 8634. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44522-8_16
Download citation
DOI: https://doi.org/10.1007/978-3-662-44522-8_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44521-1
Online ISBN: 978-3-662-44522-8
eBook Packages: Computer ScienceComputer Science (R0)