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

• машина тьюринга
• недетерминированные программы
• класс сложностей
• логарифмическая память
• сложность вычислений
• универсальная алгебра