scientific article; zbMATH DE number 4041256

From MaRDI portal
Publication:3779737





Denote by \({\mathcal L}\), respectively \({\mathcal N}{\mathcal L}\), the class of those languages \(A\subset \{0,1\}\) * for which there exist a polynomial p(n), a string of words \(\alpha_ n\subset \{0,1\}\) * with \(| \alpha_ n| <p(n)\) for any \(n\in {\mathbb{N}}\), and a deterministic, respectiv nondeterministic, Turing machine M such that \(w\in A\), \(| w| =n\), iff M accepts w{\#}\(\alpha\) \({}_ n\). The classes \({\mathcal L}\) and \({\mathcal N}{\mathcal L}\) are called nonuniform classes. A branching program is a directed acyclic graph where each node has outdegree 2 or 0 and it is labelled by a variable from a set X. There is a starting node \(n_ 0\) and the activity of a branching program can be described as follows. Starting from \(n_ 0\), the value of the variable from current node is tested: if it is 0 then the left successor becomes current node and is it 1 then the right successor becomes current node. A set A is accepted by a branching program P if for any \(w\in \{0,1\}\) * the path traced under w halts at a node with outdegree 0 and the node is labelled by \(\chi_ A(w)\), where \(\chi_ A\) is the characteristic function of A. The correspondence between languages and problems is made in usual way. Denote by \({\mathcal P}_{BP}\) the class of problems whose instances are accepted by branching programs. It is known that \({\mathcal L}={\mathcal P}_{BP}\). A branching program P is called 1-time-only nondeterministic if each variable is tested once on any path from \(n_ 0\) to a node with outdegree 0. Denote by \({\mathcal P}_{1-nBP}\) the class of problems computed by 1-time-only nondeterministic programs. In the paper it is proved that \({\mathcal N}{\mathcal L}={\mathcal P}_{1-nBP}\). Then, a partial order \(\leq\) is defined on the class of the problems and a set \(GAP^{(1,k)}\) that is \(\leq\)-complete for the class of problems computable by polynomial-size branching programs with width k, \({\mathcal N}{\mathcal C}^ 1,\) is constructed. This result makes the completeness of the graph accessibility problem for \({\mathcal N}{\mathcal L}\) more transparent. In the final of the paper, the \(\leq\)-closure of the classes \({\mathcal L}\), \({\mathcal N}{\mathcal L}\), \({\mathcal N}{\mathcal C}^ 1 \)and some \(\leq\)-hereditary properties are proved.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3779737)