Computer science: In your opinion, does P=NP?

Post Reply New Topic

Where do you stand on the P vs NP problem?
In your opinion, does P=NP?

For those who haven't heard of this problem:
https://en.wikipedia.org/wiki/P_versus_NP_problem

Way beyond my pay grade.

But I cant resist asking one question.

What is the difference between "verifying" a problem, and "solving" a problem.?

Can someone give an examples of doing one thing without also doing the other?

Verifying a problem means checking whether some solution to a problem is correct.
Solving a problem, in this context, means providing an algorithm which would be able to solve a problem in polynomial time (that is, the number of instructions used grows in a polynomial manner in relation to the input size).

Verifying a problem involves a yes or no answer (in other words, it's a decision problem). But it isn't necessarily the case for solving a problem.

A pracritcal example:
Verifying whether the solution 2 is correct for the relation x + 3 = 5 involves just computing 2 + 3 and checking whether it equals to 5. Then, the algorithm either tells us that "yes", it is the case, or "no", it isn't the case, that x = 2. In this case, the algorithm would respond with a "yes".
Solving x + 3 = 5 is different though. It involves more steps - one has to use basic algebra to find the solution:
x + 3 = 5
x = 5 - 3
x = 2

The class of problems which can be solved in polynomial time are called P.
The class of problems which can have their solutions checked in polynomial time are called NP.

There's also a class of problems called NP-hard problems. NP-hard problems are basically problems which are at least as difficult as NP problems.
And another, very interesting class is called NP-complete problems. NP-complete problems are problems which are both NP-hard and NP.

There's a wonderful theorem called the Cook-Levin theorem. It basically shows that all NP problems can be reduced to a one specific type of problem, called the boolean satisfiability problem, which happens to be NP-complete.

So if it was demonstrated that the boolean satisfiability problem can be solved in polynomial time, it would mean that P=NP (the opposite would be true in other case). Why? Because since every problem in NP can be reduced to that problem, and that problem could be solved in polynomial time, it would also mean that every NP problem would be solveable in polynomial time.

Any questions?

Verify means I give you the solution and you plug it in to whatever equations and see that the solution really is the solution. That is much easier than finding the solution with no clues. Or in solving a problem you enumerate (i.e. list) possible solutions and try each one as you go along. Even if the problem has a solution a brute force enumeration could take a long, long time and require a lot of computation. This would imply the effort required is an exponential function of the number of variables. Think of the traveling salesman problem. If I gave you a network with 1000 nodes it would take an enormous amount of computation to generate and evaluate the time for each path. In principle you you eventually find a least time problem but it would take a long, long time to do so.