Theoretical Computer Science
cc.complexity-theory sat oracles
Updated Thu, 16 Jun 2022 03:31:01 GMT

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

## Solution

Precomputation is often related to the class P/poly 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 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.