Syntactical characterization of nondeterministic logspace complexity class
https://doi.org/10.15514/ISPRAS-2014-26(2)-13
Abstract
NL is defined as the class of languages recognizable by logspace nondeterministic Turing machines. One of the main unsolved problems in complexity theory is that of relation between classes P and NL. It is known that NL is contained in P, since there is a polynomial-time algorithm for 2-satisfiability, but it is not known whether NL = P or whether NL = L. A possible approach to these problems can be based on searching for an alternative suitable definition of the class NL. Taitslin et al. propose such a definition in terms of nondeterministic programs. The syntax of such programs is similar to that of usual computer programs. Each nondeterministic program takes a finite universal algebra as input. Taitslin et al. defined a class of languages recognizable by such programs and proved that this class is a subclass of NL. In the present paper, we slightly modify their syntactical definition. Namely, we modify a definition of nondeterministic program input and give a new definition of a language recognized by a given program. We prove that the class of languages recognizable by nondeterministic programs according to our definition is just NL.
References
1. Cook S.A. Variations on push-down machines In Proc. 1st ACM Symp. on Theory of Computing, pp. 229–232, 1969.
2. Cook S.A. Characterizations of push–down machines in terms of time–bounded computers Journal of the ACM, 18(1), pp. 4–18, 1971.
3. Cook S.A. Senti R. Storage requirements for deterministic polynomial time recognizable languages Journal of Computer and System Sciences, 13(1), pp. 25–37, 1976.
4. Immerman N. Nondeterministic space is closed under complementation, SIAM Journal on Computing 17, pp. 935–938, 1988.
5. Savitch W.J. Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4 (2), pp. 177–192, 1970.
6. Papadimitriou C. Computational Complexity. Boston: Addison-Wesley. ISBN 0-201-53082-1, 1994.
7. Arora S., Barak B. Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4, 2009.
8. Stolboushkin A.P., Taitslin M.A. Dinamicheskie logiki. [Dynamic logics] Kibernetika i vychislitel'naya tekhnika [Cybernetics and computer technology] V.A. Melnikov (editor). Moscow, Nauka, pp. 180–230, 1986 (in Russian).
Review
For citations:
Nosov D.A. Syntactical characterization of nondeterministic logspace complexity class. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(2):275-296. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(2)-13
Email this article 