Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

The hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

NP-complete problems have two properties:

  1. They are in the NP complexity class (can be solved by nondeterministic Turing-machine)
  2. They are NP-hard (there is a reduction from any other NP problem to them)

A polynomial-time solution for any specific NP-complete problem will settle the $P=NP$ question affirmatively: any other problem in NP can be reduced to the specific problem of which a solution exists, and thus be solved.

Related tags

history | excerpt history