# What is known about NP hard problems that access preprocessed information?

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.

• Then you're asking about what can be solved in $\mathsf{P^{\oplus P}}$ ? Dec 29, 2011 at 23:20
• @Suresh Venkat: I realized that my idea fails for large enough problems. I guess that would have been in $P^{⊕P}$. Dec 30, 2011 at 0:29