scientific article; zbMATH DE number 4041256
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.
- Nonuniform complexity classes specified by lower and upper bounds
- Expressibility and Nonuniform Complexity Classes
- Separating NE from some nonuniform nondeterministic complexity classes
- Separating NE from Some Nonuniform Nondeterministic Complexity Classes
- Completeness for nondeterministic complexity classes
- On a complexity hierarchy between L and NL
- Separation of deterministic, nondeterministic and alternating complexity classes
- scientific article; zbMATH DE number 3917710
- scientific article; zbMATH DE number 4003531
- UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
- The power of nondeterminism in polynomial-size bounded-width branching programs
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- Reachability and the power of local ordering
- On arithmetic branching programs
- scientific article; zbMATH DE number 4209586 (Why is no real title available?)
- Expressibility and Nonuniform Complexity Classes
- Arithmetizing Classes Around NC 1 and L
- scientific article; zbMATH DE number 3987266 (Why is no real title available?)
- scientific article; zbMATH DE number 4051004 (Why is no real title available?)
- scientific article; zbMATH DE number 4070311 (Why is no real title available?)
- scientific article; zbMATH DE number 17815 (Why is no real title available?)
- scientific article; zbMATH DE number 176869 (Why is no real title available?)
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- Some classes of languages in \(NC^ 1\)
- On oblivious branching programs of linear length
- Polynomial size \(\Omega\)-branching programs and their computational power
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
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)