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

##### MSC:
 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
##### Keywords:
computation trees; polynomial ambiguity