P vs NP: Exploring the difficulty of solving problems

@ Technical Discussion

Intro

P and NP are used to describe the time required to solve problems: polynomial time or non-deterministic polynomial time.

Classifying a problem as P or NP helps determine whether it can be solved in a reasonable amount of time — i.e., whether the running time does not explode as the input size grows. Historically many problems that were only known to be in NP were later found to have polynomial-time algorithms and thus proven to be in P, e.g., primality testing🔗. However, there is currently no proof that all NP problems are in P.

P vs NP

  • P problems
    • Can be solved quickly
    • Quickly verifiable
  • NP problems
    • Not known whether they can be solved quickly
    • Quickly verifiable

Here “quick” refers to whether a problem can be solved for any input in polynomial time; for example, Big O🔗 notation indicates:

  • Constant time: O(1)
  • Logarithmic time: O(log n)
  • Linear time: O(n)
  • Linearithmic time: O(n log n)
  • Quadratic time: O(n²)
  • Cubic time: O(n³)

Example of a P problem: Sorting

Given [3, 1, 4, 1, 5, 9], sort in ascending order.

  • Solve: use a sorting algorithm (e.g., merge sort🔗), O(n log n).
  • Verify: scan once to confirm each number ≤ the next, O(n).

Example of an NP problem: Subset Sum

Given [3, 7, 1, 8, 5], is there a subset whose sum equals 14?

  • Solve: try all subsets; there are 2ⁿ possibilities, so it explodes as n grows. There is currently no known polynomial-time solution.
  • Verify: given [1, 5, 8], compute 1+5+8=14, O(n).

Reducibility

If problem A can be transformed into problem B, then B is at least as hard as A

Imagine you have a perfect translator (a function) that can turn a “French problem (A)” into an “English problem (B)”:

Because with the translator any French problem can be turned into an English one to solve; so if you can solve the English problem you can solve all the French problems. This means the English problem’s difficulty encompasses the French problem.

Terminal window
# A can be transformed into B within "polynomial time".
A ≤p B

NPC NP-Complete

The hardest problems within NP
  • Is an NP problem
  • Any NP problem can be reduced to this problem in polynomial time

Determining whether P equals NP can be decided by solving an NP-Complete problem, because all NP problems can be reduced to an NPC problem.

NP-Complete problem example: SAT (Boolean Satisfiability Problem)

All NP problems ≤p SAT

Is there an assignment of true/false values to A, B, C that makes the formula true?

(A ∨ ¬B) ∧ (¬A ∨ C) ∧ (B ∨ ¬C)
  • Solve: in the worst case enumerate all 2ⁿ assignments; there is no known polynomial-time solution.
  • Verify: given an assignment, substitute and evaluate to confirm in O(n).

Conclusion

P = NP? It asks whether “being able to quickly verify an answer” is the same as “being able to quickly find an answer”.

Further reading