How would you quantify P vs NP?

627 views

How would you quantify P vs NP?

In: Mathematics

2 Answers

Anonymous 0 Comments

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.

You are viewing 1 out of 2 answers, click here to view all answers.