### News

## Syntactical characterization of nondeterministic logspace complexity class.

#### 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

#### 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