<p>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. </p>

<p>Fooling around the complexity zoo, it seems that such a class has already been defined: <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modp" rel="nofollow">http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modp</a> and <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modkp" rel="nofollow">http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modkp</a> , depending on how you choose N.</p>

CC BY-SA 3.0
2011-12-10T00:06:33.100Z
2011-12-10T00:06:33.100Z
chazisop
<p>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".</p>

CC BY-SA 3.0
2011-12-06T21:46:08.130Z
See $\oplus P$, which is the class when $N = 2$.
David Harris
CC BY-SA 3.0
2011-12-06T22:11:00.427Z
Wikipedia links this, "Parity P", as http://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?
Matt Groff
CC BY-SA 3.0
2011-12-06T23:31:24.943Z
@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).
Matt Groff
CC BY-SA 3.0
2011-12-06T23:46:07.293Z
Technically, the oracle has information that is 100% correct all of the time.  It gets the total number of satisfying truth assignments, which I'll call $T$, but with a twist.  This number is given to the oracle modulo a number $N$.  So this number is equivalent to the total number of truth assignments.  Then, the oracle decides if the problem can be satisfied.  Well, if the number the oracle has is nonzero, then it can surely be satisfied.  However, if the $T \equiv 0 \bmod N$, we don't know if the problem can be satisfied or not.  So O(1/N) is just a general worst-case estimate.
Matt Groff
CC BY-SA 3.0
2011-12-10T18:56:10.153Z
(1) It is confusing to describe an oracle which answers the number of satisfying assignments modulo a certain number m as “oracle allowing errors,” because it does its job correctly without errors.  (2) I do not know what it means for an oracle to be relativizing or nonrelativizing.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-11T01:47:09.647Z
@Tsuyoshi Ito: What I was trying to get at was if this oracle's existence would mean that it would not be able to (help) solve an NP hard problem in polynomial time.  Sorry the description of the oracle was lacking.
Matt Groff
<cc.complexity-theory><sat><oracles><relativization>
Can an oracle allowing errors be non-relativizing?
Matt Groff
# Can an oracle allowing errors be non-relativizing?

(Asked by: username_0 on 2011-12-06)

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".

**Tags:** cc.complexity-theory, sat, oracles, relativization
> **Comments:**
> **username_1**: See $\oplus P$, which is the class when $N = 2$.  
> **username_0**: Wikipedia links this, "Parity P", as http://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?  
> **username_0**: @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).  
> **username_0**: Technically, the oracle has information that is 100% correct all of the time.  It gets the total number of satisfying truth assignments, which I'll call $T$, but with a twist.  This number is given to the oracle modulo a number $N$.  So this number is equivalent to the total number of truth assignments.  Then, the oracle decides if the problem can be satisfied.  Well, if the number the oracle has is nonzero, then it can surely be satisfied.  However, if the $T \equiv 0 \bmod N$, we don't know if the problem can be satisfied or not.  So O(1/N) is just a general worst-case estimate.  
> **username_2**: (1) It is confusing to describe an oracle which answers the number of satisfying assignments modulo a certain number m as “oracle allowing errors,” because it does its job correctly without errors.  (2) I do not know what it means for an oracle to be relativizing or nonrelativizing.  
> **username_0**: @Tsuyoshi Ito: What I was trying to get at was if this oracle's existence would mean that it would not be able to (help) solve an NP hard problem in polynomial time.  Sorry the description of the oracle was lacking.  

---

## 1 answers

### Answer by username_3 on 2011-12-10. Score: 3 | Accepted answer

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.


---

