zbMATH — the first resource for mathematics

Using inductive counting to simulate nondeterministic computation. (English) Zbl 0747.68015
Mathematical foundations of computer science, Proc. 15th Symp., MFCS ’90, Banská Bystrica/Czech. 1990, Lect. Notes Comput. Sci. 452, 187-194 (1990).
[For the entire collection see Zbl 0731.00026.]
This paper is a short version of a detailed forthcoming article of the same authors. A language \(L\) belongs to NSPACE-AMBIGUITY\([s(n),a(n)]\) if \(L\) is acceptable by a nondeterministic \(s(n)\) space-bounded Turing machine the computation trees of which have \(\leq a(n)\) computation paths leading from the start configuration to any configuration that appears in the trees. The constructability of a function will be understood as in J. Balcázar, J. Díaz, and J. Gabarró [Structural complexity, I. Springer-Verlag (1988; Zbl 0638.68040)]. The authors describe, in short, a new technique based on N. Immerman [SIAM Comput. 17(5), 935-938 (1988; Zbl 0668.68056)] and R. Szelepcsényi [Acta Inf. 26(3), 279-284 (1988; Zbl 0649.68055)]. The authors show that for all functions \(s(n)\) and \(a(n)\) if \(a(n)\) is constructible so that \(a(n)=O(2^{s(n)})\) and \(s(n)\geq\log(n)\), then NSPACE-AMBIGUITY\([s(n),a(n)]\) is contained in the class of languages accepted by \(s(n)\) a space bounded unique Turing machine.

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)