<p>Precomputation is often related to the class <a href="http://en.wikipedia.org/wiki/P/poly">P</a><a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#ppoly">/poly</a> which captures problems solvable in polynomial time by Turing machines with access to some poly-sized <em>advice string</em>, that only depends on the <em>size</em> of the instance, but not the instance itself. The <a href="http://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem">Karp-Lipton theorem</a> states, that NP is not contained in P/poly, unless the PH collapses to the second level, which is considered unlikely by many complexity theorists.</p>

CC BY-SA 3.0
2011-12-29T20:31:42.760Z
To be more precise, the oracle counts the total number of satisfying solutions, and returns this number mod p  - see this question: http://cstheory.stackexchange.com/questions/9319.
Matt Groff
CC BY-SA 3.0
2011-12-29T23:20:05.817Z
Then you're asking about what can be solved in $\mathsf{P^{\oplus P}}$ ?
Suresh Venkat
CC BY-SA 3.0
2011-12-30T00:29:19.307Z
@Suresh Venkat: I realized that my idea fails for large enough problems.  I guess that would have been in $P^{⊕P}$.
Matt Groff
CC BY-SA 3.0
2011-12-29T19:11:32.103Z
2011-12-29T19:11:32.103Z
Martin Schwarz
<p>Please accept my apologies ahead of time since I fear that this isn't an adequate question for cstheory.  I plan on releasing my ideas to get feedback, but I don't know if my target audience will include state-of-the-art reaseachers.  I'd like to know more about the research that is already out there concerning this question.</p>

<p>Essentially, what I think I've discovered is an oracle.  The oracle must be precomputed, which will probably take an exponential amount of time.  However, once computed, it can essentially answer any question about 3-SAT fast.  In other words, it can then solve any 3-SAT problem in polynomial time/space.  I'm wondering what has been researched in this scenario.</p>

<p><strong>MY ORIGINAL QUESTION</strong></p>

<p>As an armchair cstheory enthusiast, I'm now working on a way to preprocess 3-SAT.  I'm wondering how this relates to research on oracles and related ideas.  Please let me briefly describe my method, or conjectured approach.  </p>

<p>We take a given problem size.  Essentially we have exactly $2^n$ clauses and $v$ variables.  (Note that problems smaller than this can automatically be solved, too.)  After we know the maximum amount of clauses, we can preprocess information for every possible 3-SAT clause, given the information just stated.  This may take an exponential amount of information, even for each individual clause.</p>

<p>However, once the information is preprocessed, we can solve 3-SAT fast.  In other words, using this pre-computed database, which is polynomial in size, we can determine satisfiability for a particular instance as well as generate a certificate in polynomial time and space.</p>

<p>So if I'm correct, we use an oracle and we can ensure that 3-SAT can be solved in polynomial time and space.  However, the oracle itself takes a possibly exponential amount of time and space to compute.</p>

<p>My question is where in the literature can I find information concerning pre-computing information (like I have described) to solve NP-hard and NP-complete problems in polynomial time and space?  What is known about this approach?  I don't mean to be vague, but I'm simply trying to find out what has been considered about an approach like this in the past.  I plan on eventually releasing my ideas if they are interesting, but I would like to know if they have already been researched.</p>

<cc.complexity-theory><sat><oracles>
What is known about NP hard problems that access preprocessed information?
Matt Groff
# What is known about NP hard problems that access preprocessed information?

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

Please accept my apologies ahead of time since I fear that this isn't an adequate question for cstheory. I plan on releasing my ideas to get feedback, but I don't know if my target audience will include state-of-the-art reaseachers. I'd like to know more about the research that is already out there concerning this question.

Essentially, what I think I've discovered is an oracle. The oracle must be precomputed, which will probably take an exponential amount of time. However, once computed, it can essentially answer any question about 3-SAT fast. In other words, it can then solve any 3-SAT problem in polynomial time/space. I'm wondering what has been researched in this scenario.

**MY ORIGINAL QUESTION**

As an armchair cstheory enthusiast, I'm now working on a way to preprocess 3-SAT. I'm wondering how this relates to research on oracles and related ideas. Please let me briefly describe my method, or conjectured approach.

We take a given problem size. Essentially we have exactly $2^n$ clauses and $v$ variables. (Note that problems smaller than this can automatically be solved, too.) After we know the maximum amount of clauses, we can preprocess information for every possible 3-SAT clause, given the information just stated. This may take an exponential amount of information, even for each individual clause.

However, once the information is preprocessed, we can solve 3-SAT fast. In other words, using this pre-computed database, which is polynomial in size, we can determine satisfiability for a particular instance as well as generate a certificate in polynomial time and space.

So if I'm correct, we use an oracle and we can ensure that 3-SAT can be solved in polynomial time and space. However, the oracle itself takes a possibly exponential amount of time and space to compute.

My question is where in the literature can I find information concerning pre-computing information (like I have described) to solve NP-hard and NP-complete problems in polynomial time and space? What is known about this approach? I don't mean to be vague, but I'm simply trying to find out what has been considered about an approach like this in the past. I plan on eventually releasing my ideas if they are interesting, but I would like to know if they have already been researched.

**Tags:** cc.complexity-theory, sat, oracles


---

## 1 answers

### Answer by username_1 on 2011-12-29. Score: 5 | Accepted answer

Precomputation is often related to the class [P](http://en.wikipedia.org/wiki/P/poly)[/poly](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#ppoly) which captures problems solvable in polynomial time by Turing machines with access to some poly-sized *advice string*, that only depends on the *size* of the instance, but not the instance itself. The [Karp-Lipton theorem](http://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem) states, that NP is not contained in P/poly, unless the PH collapses to the second level, which is considered unlikely by many complexity theorists.

> **Comments:**
> **username_0**: To be more precise, the oracle counts the total number of satisfying solutions, and returns this number mod p  - see this question: http://cstheory.stackexchange.com/questions/9319.  
> **username_2**: Then you're asking about what can be solved in $\mathsf{P^{\oplus P}}$ ?  
> **username_0**: @username_2: I realized that my idea fails for large enough problems.  I guess that would have been in $P^{⊕P}$.  

---

