How would you quantify P vs NP?
In: Mathematics
For a problem in math we will usually have some input. The size of that input can change how hard it is to solve the problem. We quantify how hard it is to solve that problem by counting the number of operations are required to solve it as that input gets bigger.
So a really simple example of this is a factorial. To solve a factorial we multiply a number by every single number that comes before it. So 3 factorial is 3*2*1=6. 4 factorial is 4*3*2*1=24. As you can see that each time we have to multiply the same number of items as our input, so the number of operations it takes to solve a factorial is n where n is the input. This gets more complicated with more complicated problems.
If the time it takes to solve something ends up being a polynomial then we call that a P problem. A polynomial is just the sum of some value taken to exponents with some coefficients. For instance n^2 + 2n + 3 would be a polynomial.
A lot of problems are more complicated and take much higher than polynomial time, for instance you might have a problem that grows exponentially as the input gets bigger. However sometimes you can have a problem that doesn’t have polynomial time to solve, but does take polynomial time to verify. So if you have an answer you can check it in an amount of time that is a polynomial of your input. We call these problems NP problems.
There is a theory that it’s possible that any problem that can be verified in polynomial time can also be solved in polynomial time. If anyone ever shows a way to do that it would be a very big deal in mathematics, but it would basically require you to invent a whole bunch of new concepts in math.
“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