- most researchers believe $P \neq NP$ - essence of the problem is: if it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? ![[Pasted image 20240420170234.png]] - if $P = NP$ - exponential search can always be avoided - finding proofs of mathematical assertions is in $NP$ - this is cause it's a search problem & thus in $NP$ - notably, you can check the proof mechanically line by line, with an efficient algorithm as required - $P = NP$ mean there's an efficient method to prove every theorem - eliminating need for mathematicians - if $P \neq NP$ - all NP complete problems are hard to solve - cause if one was easy to solve, then $P = NP$ - proving $P \neq NP$ has turned out to be extremely difficult, one of deepest & most important puzzles of mathematics - is one of the millennium problems from the Clay Mathematics Institute links: [[P Problems]], [[NP Problems]], [[NP Complete Problems]], [[NP Hard Problems]] https://people.eecs.berkeley.edu/~vazirani/algorithms/chap8.pdf https://www.claymath.org/millennium/p-vs-np/