On the Accepting Density Hierarchy in NP
Shlomo Moran · SIAM Journal on Computing · 1982
Let $Al$ be a polynomial time nondeterministic algorithm accepting a set A, and let $a \in A$. The “accepting density” of $Al$ for a is the ratio between the number of accepting computations and the total number of computations of $Al$ on input a. (If this ratio is $ \geqq 1/2$ for all $a \in A$, then $Al$ is a polynomial time probabilistic algorithm accepting A.) In this paper a characterization of sets in NP according to their “accepting density” is investigated. It is shown that for some relativized form of NP no general, nontrivial lower bound on the accepting density of sets in NP exists. It follows that for this relativized form the accepting density of any NP complete set for inputs of length n cannot be greater than $1/2^{n^c } $ for some fixed $c > 0$ and that NP (under that relativization) can be partitioned to infinitely many classes $C_1 ,C_2 , \cdots $, such that the accepting density of sets in $C_i $ is strictly greater, in some precise sense, than that of sets in $C_{i + 1} $. Recent works on the relationship between relativized and unrelativized proof techniques imply that to prove that any of the above results does not hold for the (unrelativized) class NP, possible at all, is probably beyond the ability of today’s techniques.