Learning P vs NP problems
March 10, 2023 · View on GitHub
Just one of the things I'm learning. https://github.com/hchiam/learning
To oversimplify, P = easy, NP = hard.
P = theoretically solvable in O(n^k) time. "Easy" to solve.
NP = theoretically verifiable in O(n^k) time. "Easy" to verify. Example: Sudoku is in NP, but does not seem to be in P.
P ⊆ NP, but is P = NP? It seems so far that P ≠ NP.
In other words, "easy" problems can be "easy" to verify. But if a solution is "easy" to verify, is there always an "easy" way to solve the problem? It seems so far that there will always exist problems that are "harder" to solve than to verify.
Diagram from https://en.wikipedia.org/wiki/P_versus_NP_problem:
