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".
$\begingroup$
$\endgroup$
8
-
$\begingroup$ See $\oplus P$, which is the class when $N = 2$. $\endgroup$– David HarrisDec 6, 2011 at 21:46
-
$\begingroup$ 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? $\endgroup$– Matt GroffDec 6, 2011 at 22:11
-
$\begingroup$ (#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? $\endgroup$– user6973Dec 6, 2011 at 23:10
-
$\begingroup$ @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). $\endgroup$– Matt GroffDec 6, 2011 at 23:31
-
$\begingroup$ 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."? $\;\;$ $\endgroup$– user6973Dec 6, 2011 at 23:35
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
When considering variations of a computation model, let alone one that is not natural and might confuse our intuition, definitions are of the essense. Your oracle might be in #P but that doesn't mean that is representative of that class. Since you have changed the definition of the function the oracle computes, you will have to either prove the new problem #P-complete or find another appropriate class for which the problem is complete.
Fooling around the complexity zoo, it seems that such a class has already been defined: http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modp and http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modkp , depending on how you choose N.
