7
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Why is it astonishing? Direct proofs (i.e., proving that you can simulate a Turing machine) tend to be very tedious to construct. It's perfectly normal in mathematics that you don't go all the way back to the basics every time but, rather, build upon existing knowledge. In this case, the existing knowledge is "SAT is NP-complete". $\endgroup$
    – David Richerby
    Commented Aug 30, 2014 at 23:19
  • $\begingroup$ @DavidRicherby actually it's very unlike mathematics. While it's true that all proofs must ultimately be traced back to some set of axioms, mathematicians are always looking to find simpler proofs that cut through the dust and smoke. Look at proofs of FLT using number theory vs group theory. Or FTA using complex analysis vs algebraic topology. $\endgroup$
    – zac
    Commented Aug 31, 2014 at 0:11
  • $\begingroup$ @DavidRicherby I don't know who said it (I think it was Gauss), but just because we're not smart enough to come up with elegant, intuitive proofs and instead have to rely on artificial/synthetic proofs, don't mean they don't exist. $\endgroup$
    – zac
    Commented Aug 31, 2014 at 0:12
  • 3
    $\begingroup$ You wouldn't try to do analysis without the intermediate value theorem or probability without Markov's inequality. In the same way, you don't try to do complexity theory without using NP-completeness of SAT. But, if you want a direct demonstration of why people use reductions from SAT to prove NP-completeness, just try to prove that 3-colourability is NP-complete by translating nondeterministic polytime Turing machines to graphs such that the graph is 3-colourable if, and only if, the machine accepts its input. Good luck! $\endgroup$
    – David Richerby
    Commented Aug 31, 2014 at 1:00
  • $\begingroup$ @DavidRicherby yes, but for the most part it's because some things in real analysis do actually depend on the IVT. The NP-Completeness of 3-colourability does not depend on SAT - it should be provable by itself (though I submit that it may be very hard) $\endgroup$
    – zac
    Commented Aug 31, 2014 at 14:29

2 Answers 2

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ If I get what you're saying..the first part of the proof of SAT is really the crux of why all NP-Complete problems are "hard"? Similar to Kuratowski's Theorem characterizing why some graphs aren't planar? The latter part is just a translation to SAT specifically? $\endgroup$
    – zac
    Commented Aug 30, 2014 at 23:55
  • $\begingroup$ I will mark correct, but really looking to answer of my comment! $\endgroup$
    – zac
    Commented Sep 3, 2014 at 3:04
  • $\begingroup$ I'm not completely sure I understand your question, but here's how I think of it: SAT, 3-coloring, and even the problem of "does this nondeterministic turing machine accept within p(n) steps", are all combinatorial problems that are basically asking the same thing but in different foreign languages. So, if you want to use a solution for one to solve another you need a translation. The crux of the cook-levin theorem is mostly just the idea that "polynomial length NTM acceptance" is itself a combinatorial problem and consequently handled in translations to SAT, etc. $\endgroup$
    – Kurt Mueller
    Commented Sep 3, 2014 at 3:49
3
$\begingroup$

Fagin's proof that model checking existential second-order logic is NP-complete is a direct reduction from an arbitrary NP Turing machine, very much like the SAT proof.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting, I'll take a look! $\endgroup$
    – zac
    Commented Aug 31, 2014 at 0:15
  • $\begingroup$ This answer needs a direct reference. $\endgroup$
    – Raphael
    Commented Sep 1, 2014 at 10:23

Your Answer

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

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