**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