I'm just starting to learn about NP-completeness. While I understand that reducibility plays a key role in this, I'm astonished how few problems I've been able to find who's proof that they are NP-Complete is not based on reduction to an existing NP-Complete problem.
While I understand these proofs are perfectly valid, you loose insight into what makes a particular problem difficult if you have to trace logic through 3, 4, 5+ reductions.
Since NP-Complete is, by definition, an equivalence class, I should be able to start with any of them; however I can only seem to find is this general strategy.
Are there any other problems with direct proofs that they are NP-Complete other than Circuit-SAT and SAT?
Asked By : zac
Answered By : Kurt Mueller
At risk of sounding like I'm avoiding the question, I claim that every reduction is a direct proof of NP-completeness, just avoiding a lot of tedious, unnecessary work.
First, let me talk a little about the proof of the Cook-Levin theorem (SAT np-completeness).
At a very high level, the cook-levin theorem proof does this:
Assume R is some problem in NP. Then, by definition, there is a nondeterministic TM $T$ that runs in $p(n)$ time and decides $R$, for $p(n)$ a polynomial.
Then, it is sufficient to show that for any $x$, we can construct in polytime a boolean formula $B$ such that $B$ is satisfiable if and only if $T$ accepts $x$ (within $p(|x|)$ steps, by assumption of $T$).
Finally, by taking the formal definition of a nondeterministic turing machine and translating it into the language of a SAT instance, we construct a formula that is true only if $T$ accepts $x$ within $p(|x|)$ steps. This is a tedious and difficult process, which you can read about here http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem#Proof
Anyways, the point of this explanation is the last paragraph: notably, that the only nontrivial part of this proof is taking the parts of a NTM and putting it in the language of a SAT instance. But, this is essentially what a reduction is!
For example, when you write a reduction from SAT to 3-coloring, what you are showing is that a SAT instance can be translated into a 3-coloring instance -- and this gives you a direct proof of np-completeness, because we already have a translation from a p(n) time NTM into a SAT instance.
So, cook-levin tells us how to make boolean formulas from an NTM, and a 3-coloring reduction tells us how to make vertices and edges from boolean formulas. Put these together, and you get a direct translation from an NTM into vertices and edges, which is exactly what you're looking for. It just happens to be tedious to deal with all the annoying little pieces of the NTM formalism, so no one likes to deal with that. It's much easier to do a reduction from SAT than a 'reduction' from NTM.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/29526
0 comments:
Post a Comment
Let us know your responses and feedback