On the relativized power of additional accepting paths
Richard Beigel · 2003
The author defines U/sub k(n)/P 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. Then P contained in UP contained in U/sub k(n)/P contained in U/sub k(n)+1/P contained in FewP $4 for every polynomial k(n)>or=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. The author considers whether any of the containments is proper.>