# Can an oracle allowing errors be non-relativizing?

I am experimenting with k-SAT. I'm using an oracle that returns the total number of satisfiable truth assignments, which is in #P. The interest here is that this total is returned modulo a natural number, say N. There is therefore a 1/N probability that the oracle mistakes a satisfiable problem for one with zero satisfiable truth assignments. I'm wondering if this oracle could be non-relativizing. I'm also wondering if there has been research concerning oracles with similar types of "errors".

• See $\oplus P$, which is the class when $N = 2$. Dec 6 '11 at 21:46
• Wikipedia links this, "Parity P", as en.wikipedia.org/wiki/Parity_P. However, with enough oracles and enough numbers $N_1, N_2, N_3, \dots$ we should be able to solve for the total number of satisfiable truth assignments using Chinese Remainder Theorem. This would give the oracle the power of #P. So I am wondering where this puts things. Is there a construction where #P=P? Dec 6 '11 at 22:11
• (#P)^QBF = P^QBF . $\;$ Also, how do you know that the number of instances whose number of satisfying assingments is a multiple of N is approximately 1/N of the number of instances total?
– user6973
Dec 6 '11 at 23:10
• @Ricky Demer: Roughly speaking. We get the result modulo a number N. The chances that this number is zero is approximately 1/N. We can assume, in the worst case, that this zero result is always wrong. So in the worst case, we have an error probability 1/N. I guess I should have said that the error probability is O(1/N). Dec 6 '11 at 23:31
• I don't see how to get that either. $\:$ Do you mean "Heuristically, the oracle will make a mistake on 1/N of the instances."? $\;\;$
– user6973
Dec 6 '11 at 23:35