How would you quantify P vs NP?
In: Mathematics
“quantify”? Easy peasy. Just show them some examples of problems that can be solved quickly (P) and then some that are hard to solve but can be verified quickly(NP). So…
P: Any simple algorithm, like… “what’s 4 * x^2 + 1/2*x + 7 when x = 5?”
NP: subset sum problem: given a set of integers, does any non-empty subset of them add up to zero?
[3,-12,7,-5,21,-25,45,-129,234,-274,312,-345]
Have them count every comparison, and every math operation they perform to solve it. uh, 5 for P and… a lot for NP. Now give it to another group and have them verify. How many steps does it take for verify the first? Should still be 5 for P, and only 4 for NP once you know -12+312-345+45=0. Boom, quantified.
Latest Answers