Npcompleteness And Reducibility
NPcompleteness and reducibility: Perhaps the most compelling reason why theoretical computer scientists believe that P ≠ NP is the existence of the class of "NPcomplete" problems. This class has the surprising property that if any NPcomplete problem can be solved in polynomial time, then every problem in NP has a polynomialtime solution, that is, P = NP. Despite years of study, though, no polynomialtime algorithm has ever been discovered for any NPcomplete problem.
The language HAMCYCLE is one NPcomplete problem. If we could decide HAMCYCLE in polynomial time, then we could solve every problem in NP in polynomial time. In fact, if NP  P should turn out to be nonempty, we could say with certainty that HAMCYCLE ∈ NP  P.
The NPcomplete languages are, in a sense, the "hardest" languages in NP. In this section, we shall show how to compare the relative "hardness" of languages using a precise notion called "polynomialtime reducibility." Then we formally define the NPcomplete languages, and we finish by sketching a proof that one such language, called CIRCUITSAT, is NPcomplete. In NPcompleteness proofs and NPcomplete problems, we shall use the notion of reducibility to show that many other problems are NPcomplete.
Reducibility: Intuitively, a problem Q can be reduced to another problem Q′ if any instance of Q can be "easily rephrased" as an instance of Q′, the solution to which provides a solution to the instance of Q. For example, the problem of solving linear equations in an indeterminate x reduces to the problem of solving quadratic equations. Given an instance ax b = 0, we transform it to 0x^{2} ax b = 0, whose solution provides a solution to ax b = 0. Thus, if a problem Q reduces to another problem Q′, then Q is, in a sense, "no harder to solve" than Q′.
Returning to our formallanguage framework for decision problems, we say that a language L^{1} is polynomialtime reducible to a language L_{2}, written L_{1} ≤_{P} L_{2}, if there exists a polynomialtime computable function f : {0, 1}* → {0,1}* such that for all x {0, 1}*,
We call the function f the reduction function, and a polynomialtime algorithm F that computes f is called a reduction algorithm.
Figure 34.4 illustrates the idea of a polynomialtime reduction from a language L_{1} to another language L2. Each language is a subset of {0, 1}*. The reduction function f provides a polynomialtime mapping such that if x ∈ L_{1}, then f(x) ∈ L_{2}. Moreover, if x ∉ L_{1}, then f (x) ∉ L_{2}. Thus, the reduction function maps any instance x of the decision problem represented by the language L_{1} to an instance f (x) of the problem represented by L_{2}. Providing an answer to whether f(x) ∈ L_{2} directly provides the answer to whether x ∈ L_{1}
Polynomialtime reductions give us a powerful tool for proving that various languages belong to P.
NPcompleteness: Polynomialtime reductions provide a formal means for showing that one problem is at least as hard as another, to within a polynomialtime factor. That is, if L_{1} ≤_{P} L_{2}, then L_{1} is not more than a polynomial factor harder than L_{2}, which is why the "less than or equal to" notation for reduction is mnemonic. We can now define the set of NPcomplete languages, which are the hardest problems in NP.
A language L ⊆ {0, 1}* is NPcomplete if

L ∈ NP, and

L′ ≤_{P} L for every L∈ NP.
If a language L satisfies property 2, but not necessarily property 1, we say that L is NPhard. We also define NPC to be the class of NPcomplete languages.
As the following theorem shows, NPcompleteness is at the crux of deciding whether P is in fact equal to NP.
Proof Suppose that L ∈ P and also that L ∈ NPC. For any L′ ∈ NP, we have L′ ≤_{P} L by property 2 of the definition of NPcompleteness. we also have that L′ ∈ P, which proves the first statement of the theorem.
To prove the second statement, note that it is the contrapositive of the first statement.
It is for this reason that research into the P ≠ NP question centers around the NPcomplete problems. Most theoretical computer scientists believe that P ≠ NP, which leads to the relationships among P, NP, and NPC shown in Figure 34.6. But, for all we know, someone may come up with a polynomialtime algorithm for an NPcomplete problem, thus proving that P = NP. Nevertheless, since no polynomialtime algorithm for any NPcomplete problem has yet been discovered, a proof that a problem is NPcomplete provides excellent evidence for its intractability.
Figure 34.6: How most theoretical computer scientists view the relationships among P, NP, and NPC. Both P and NPC are wholly contained within NP, and P ∩ NPC = Ø.