0
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Matt Groff
    Dec 29, 2011 at 20:31
  • $\begingroup$ Then you're asking about what can be solved in $\mathsf{P^{\oplus P}}$ ? $\endgroup$
    – Suresh Venkat
    Dec 29, 2011 at 23:20
  • $\begingroup$ @Suresh Venkat: I realized that my idea fails for large enough problems. I guess that would have been in $P^{⊕P}$. $\endgroup$
    – Matt Groff
    Dec 30, 2011 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.