P, NP, NP-complete

  • A problem is in class P if its solution may be found in polynomial time.
  • A problem is in class NP if its solution may be verified in polynomial time.
  • A problem in P is in NP by definition, but the converse may not be the case.
  • NP-complete is a family of NP problems for which you know that if one of them has a polynomial solution then everyone of them has.
  • Examples of NP-complete problems: traveling salesman, knapsack, graph coloring.
  • Once you've reduced a problem to NP-complete, you know to give up on an efficient fast algorithm and to start looking at approximations.
  • For NP-complete problems, no polynomial-time algorithms are known for solving them (although they can be verified in polynomial time).
  • The most notable characteristic of NP-complete problems is that no fast solution to them is known.
  • NP-hard: non-deterministic polynomial time.

results matching ""

    No results matching ""