how were the first NP-complete problems shown to be NP-complete?

Question

From the wikipedia entry on NP-Complete:

"The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it"

I'm pretty sure that I understand this: If I have a problem, I can show that it is NP-Complete if I:

1. show that it is in NP (a solution to the problem can be verified in polynomial time on a non-deterministic Turing machine)

2. Show that a problem already known to be NP-Complete can be 'reduced' to the new problem

So, my question is, how were the first NP-complete problems 'proven' to be NP-complete? At one time, the set of known NP-complete problems must have been zero, and this would have made it impossible to resort to step 2 in the above process.

This makes me think that there is a different method for proof which I'm not aware of. Either that, or maybe the whole NP-complete property is 'assumed' for certain problems due to lack of a known polynomial time solution. (actually, having written this, I wouldn't be surprised if this is the case, but I'd like some guru-feedback either way).

Answer 1

Cook's Theorem

The class NP can be defined as the class of problems decidable by a nondeterministic Turing machine in polynomial time. This theorem shows that SAT is NP-complete by encoding the operation of any nondeterministic Turing machine by a boolean formula, in such a way that the machine accepts if and only if that formula is SATisfiable.

Historically speaking, the notion of NP-completeness was introduced in Richard Karp's seminal paper (Reducibility Among Combinatorial Problems), where he defined NP-completeness, used Cook's theorem, and in one big shot, proved 21 problems NP-complete.

Answer 2

To give you the essence of the proof (which is several pages of hard going in Garey & Johnson's Computers and Intractibility):

Any computational problem can be expressed as a Turing machine.

It is possible to express the Turing machine as a logic problem, satisfying certain complexity constraints.

Therefore, if you can solve the logic problem in polynomial time, you can solve the Turing machine problem in polynomial time.

This (along with some other considerations) shows that if you can solve the logic problem in polynomial time, you can solve any NP problem in polynomial time. This being the definition of NP-complete, the logic problem is therefore NP-complete, and can be used as a basis for other problems.

The logic problem used is called Satisfiability (often abbreviated to SAT). Given a series of clauses of the form (A or not-B or not-C) (clauses consisting of any number of propositions and negations of propositions connected by logical or), is there an assignment of truth values to the propositions that makes all the clauses true?

NP-completeness is a well-defined property. The only reason you'd be in doubt about a problem being NP-complete is that you thought you could reduce another NP-complete problem to it, but haven't managed to find a convenient problem or derive a proof yet.

The question is not whether NP-complete problems exist, or how to prove a problem is NP-complete, but what that means. Nobody has yet produced a polynomial-time algorithm to solve an NP-complete problem, and nobody has proved that such an algorithm can't exist. Whether or not P=NP, we certainly don't have good algorithms to solve any NP-complete problem.

This is one of the Claypool Foundation's Millenium Problems, so if you can come up with a proof that has been eluding some very bright people for quite a few years, there's a million dollars in it for you.

Answer 3

Just a comment on this problem in general, please bear with me. I guess NP-completeness is important for problems like code-breaking where the value of the answer far outweighs the difficulty or expense of solving the problem.

Problems can't be solved without information. If the information that comes into an algorithm is sufficiently constricted, then it will take a long time. For example, you could say a linear search algorithm takes exponential time if you count N as the number of bits in the resulting index. Each comparison is nearly always false, so it yields very little information, so naturally it is slow.

Binary search, on the other hand, takes linear time in the number of index bits, because each comparison yields nearly a whole bit of information (because the 2 outcomes are nearly equally likely).

Any time I've heard that a problem is really hard, in a practical sense, it has almost always been the case that it is stated in terms that are too general, starving it of input information, often for no good reason except generality.