- 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