On the Relativized Power of Additional Accepting Paths

Title: On the Relativized Power of Additional Accepting Paths

Authors: Richard Beigel

Abstract: The class UP is the class of languages in NP that are accepted by machines with at most one accepting path on each input. We define UP_k(n) as the class of languages in NP that are accepted by machines with at most k(n) accepting paths on each input of length n. Obviously

P ⊆ UP ⊆ UP_k(n) ⊆ UP_k(n)+1 ⊆ FewP ⊆ NP for every polynomial k(n) ≥ 2, where FewP is the class of languages in NP that are accepted by machines with a polynomial-bounded number of accepting paths on each input. It is an open question whether any of the containments is proper. A proper containment would imply P ≠ NP. We consider the relativized class UP_k(n)^A, and we construct an oracle A such that P^A ⊂ UP ^A ⊂ UP_k(n)^A ⊂ UP_k(n)+1^A ⊂ FewP^A ⊂ NP^A for every polynomial k(n) ≥ 2. Relative to a random oracle A, we prove that P^A ⊂ UP^A ⊂ UP_k^A ⊂ UP_k+1^A ⊂ FewP^A for every constant k ≥ 2, and we prove similar separations when k(n) is not a constant. Previously, Hartmanis and Hemachandra have shown that it is not possible to separate P^A from UP^A via uniform techniques; therefore the methods we use are necessarily novel. Unlike previous random oracle results, we use nonuniform techniques and nontrivial probability theory in order to prove the separations.

Download Full Paper