Skip to content

Latest commit

 

History

History
11 lines (10 loc) · 919 Bytes

p-np.md

File metadata and controls

11 lines (10 loc) · 919 Bytes
Raw

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.