NP-completeness P versus NP problem

euler diagram p, np, np-complete, , np-hard set of problems (excluding empty language , complement, belong p not np-complete)

to attack p = np question, concept of np-completeness useful. np-complete problems set of problems each of other np-problem can reduced in polynomial time, , solution may still verified in polynomial time. is, np problem can transformed of np-complete problems. informally, np-complete problem np problem @ least tough other problem in np.

np-hard problems @ least hard np problems, i.e., np problems can reduced (in polynomial time) them. np-hard problems need not in np, i.e., need not have solutions verifiable in polynomial time.

for instance, boolean satisfiability problem np-complete cook–levin theorem, instance of problem in np can transformed mechanically instance of boolean satisfiability problem in polynomial time. boolean satisfiability problem 1 of many such np-complete problems. if np-complete problem in p, follow p = np. however, many important problems have been shown np-complete, , no fast algorithm of them known.

based on definition alone not obvious np-complete problems exist; however, trivial , contrived np-complete problem can formulated follows: given description of turing machine m guaranteed halt in polynomial time, there exist polynomial-size input m accept? in np because (given input) simple check whether m accepts input simulating m; np-complete because verifier particular instance of problem in np can encoded polynomial-time machine m takes solution verified input. question of whether instance yes or no instance determined whether valid input exists.

the first natural problem proven np-complete boolean satisfiability problem. noted above, cook–levin theorem; proof satisfiability np-complete contains technical details turing machines relate definition of np. however, after problem proved np-complete, proof reduction provided simpler way show many other problems np-complete, including sudoku discussed earlier. in case, proof shows if solve sudoku in polynomial time, use complete latin squares in polynomial time. in turn gives solution problem of partitioning tri-partitite graphs triangles, used find solutions 3-sat, provides solution general boolean satisfiability. polynomial time solution sudoku leads, series of mechanical transformations, polynomial time solution of satisfiability, in turn can used solve other np-complete problem in polynomial time. using transformations this, vast class of seemingly unrelated problems reducible 1 another, , in sense same problem .