Recent Posts

Archive

Tags

The N Versus NP Problem

It has been a long time since I last posted, but now I come with a new problem that I recently learned about. As you can imagine it's called the N vs NP problem, and is essentially asking the question whether every problem whose solution can be quickly verified can also be solved quickly. And this obviously relates to computer science, because computers need to right away know how long the calculation will take. And this problem I think I am going to try using examples.

Take the function: 8 X 9 - 3.

A computer would verify this by doing 69 + 3 ÷ 9 = 8 or 69 + 3 ÷ 9 ≠ 8

Either way this calculation would only take a matter of nanoseconds to verify by a computer,

and would take exactly the same amount of time to solve normally.

But if I was to use the example 2^5 (2 to the power of 5) heres what would happen

2 X 2 X 2 X 2 X 2 = 32 to verify it would be 32 ÷ 2 ÷ 2 ÷ 2 ÷ 2 = 2

It is still the same thing and if multiplying and dividing require the same amount of time, then P = NP if Mns = Dns


What that means is P = NP if the time taken to multiply and the time taken to divide are equal. If they can both be done in polynomial time, then the result would be P= NP