Proceedings of ISP RAS


Syntactical characterization of nondeterministic logspace complexity class.

D.A. Nosov.

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.

Keywords

Turing machine; nondeterministic program; complexity class; logspace complexity; universal algebra

Edition

Proceedings of the Institute for System Programming, vol. 26, issue 2, 2014, pp. 275-296.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2014-26(2)-13

Full text of the paper in pdf (in Russian) Back to the contents of the volume