zbMATH — the first resource for mathematics

Using inductive counting to simulate nondeterministic computation. (English) Zbl 0769.68028
Summary: Immerman and SzelepcsĂ©nyi’s inductive counting technique demonstrated that, for space classes, the nondeterministic acceptance mechanism can simulate with no space penalty any reasonable acceptance mechanism based on censuses of configurations. However, the efficiency with which other acceptance mechanisms can simulate nondeterminism remains an open question. This paper uses inductive counting to study the cost of simulating nondeterminism with Valiant’s paradigm of unique computation - - nondeterministic computation in which each input generates at most one accepting computation. We show that unique computation can simulate nondeterministic computation with a space penalty logarithmic in the ambiguity of the nondeterministic computation tree. Relatedly, we show that unique AuxPDAs and restricted \(\text{SAC}^ 1\) circuits can efficiently simulate ambiguity-bounded nondeterministic computation. In particular, all nondeterministic logspace languages of polynomial ambiguity are in Weak Unamb\(\text{RAC}^ 1\), and thus are accepted by uniform, weak, unambiguous, shallow circuits.

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI