P vs. NP

The P vs. NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified (technically, verified in polynomial time) can also be solved quickly (again, in polynomial time).

P (Polynomial Time)

  • Some algorithm can provide an answer in polynomial time (opposed to exponential time).

NP (Nondeterministic Polynomial Time)

  • There is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly (in polynomial time).
  • E.g. Sudoku – Any proposed solution is easily verified, and the time to check a solution grows slowly (polynomially) as the grid gets bigger. However, all known algorithms for finding solutions take, for difficult examples, time that grows exponentially as the grid gets bigger.

NP – Complete

  • A problem in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time.
  • It is not known whether every problem in NP can be quickly solved—this is called the P vs. NP problem. But if any NP-complete problem can be solved quickly, then every problem in NP can be solved quickly because of above definition.

 

P = NP: Problems that can be verified in polynomial time can also be solved in polynomial time.  

P ≠ NP: Problems can not be solved in polynomial time, but the answer could be verified in polynomial time.

 

Here is a helpful Youtube video.

 

 

 

Sources:

 

Leave A Comment

Your email address will not be published. Required fields are marked *