complete problems shown to be NP

 

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:

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

  • 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).

    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.

    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.

    链接地址: http://www.djcxy.com/p/39968.html

    上一篇: 为什么NP方式会这样叫（和NP

    下一篇: 显示为NP的完整问题