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.

Comments (3)

  • +0 – To be more precise, the oracle counts the total number of satisfying solutions, and returns this number mod p - see this question: cstheory.stackexchange.com/questions/9319. — Dec 29, 2011 at 20:31  
  • +0 – Then you're asking about what can be solved in $\mathsf{P^{\oplus P}}$ ? — Dec 29, 2011 at 23:20  
  • +0 – @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 00:29  

External Links

External links referenced by this document:

References