- any proposed solution can be verified in polynomial time
- NP stands for nondeterministic polynomial time
- means a nondeterministic algorithm could solve the problem
- nondeterministic algorithms:
- this algorithm has the unrealistic power of guessing correctly at every step
- to prove a problem is in NP, you must show there exists a polynomial verifier for it
- all problems in NP can be solved in polynomial space
- (if it were exponential, it wouldn't be possible to read the solution in polynomial time to check)
- examples include:
- predicting how proteins fold, encrypting messages, solving Sudoku puzzles etc
https://people.eecs.berkeley.edu/~vazirani/algorithms/chap8.pdf
https://towardsdatascience.com/the-limits-of-knowledge-b59be67fd50a