I&C Journal 1993 Journal Article
Using Inductive Counting to Simulate Nondeterministic Computation
- G. Buntrock
- L.A. Hemachandra
- D. Siefkes
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 SAC1 circuits can efficiently simulate ambiguity-bounded nondeterministic computation. In particular, all nondeterministic logspace languages of polynonmial ambiguity are in WeakUnambRAC1, and thus are accepted by uniform, weak, unambiguous, shallow circuits.