NP vs P - difference between veryfing and answering

[xeon123]

Hi,

1. A yes-or-no problem is in P (Poynomial time) if it the answer can be computed in polynomial time.
2- A yes-or-no problem is in NP (Non-deterministic Poynomial time) if a yes answer can be verified in polynomial time.

I don't understand here the difference between answering and verifying a problem in polynomial time. If we can verify that a yes-or-no problem is in NP in polynomial time, doesn't means that it can be answered?

 

[jacobrhcp]

verifying: if you have a solution to a problem (like: can you solve a particular version of TSP in less then k meters?), can you then in polynomial time in the input parameters (in this case the number of nodes and arcs in the TSP network) check if it is indeed a solution that is shorter than k? - yes, that's easy.

computing: if you have a problem can you actually FIND the solution in polynomial time? No one knows for the above specified problem, but odds are you can't.

 

[SteveL27]

Hi,

1. A yes-or-no problem is in P (Poynomial time) if it the answer can be computed in polynomial time.
2- A yes-or-no problem is in NP (Non-deterministic Poynomial time) if a yes answer can be verified in polynomial time.

I don't understand here the difference between answering and verifying a problem in polynomial time. If we can verify that a yes-or-no problem is in NP in polynomial time, doesn't means that it can be answered?

It's like reading a thread on this forum. Someone asks a math question. You (or I) think about it but we can't see the solution. Some clever poster comes along and shows a perfectly clear solution. We read it line by line and we're convinced.

So we see that in practice, verifying a solution is far easier than being the first one to find a solution. That's the difference. If P = NP then finding a solution is no more difficult than verifying one. Seems unlikely to be true, but if you have a proof that P != NP you'll become famous.

 

[Office_Shredder]

A good example is the following two problems:

1) Find a factor of 123109824098231
You probably will not be able to solve this in the total amount of time you are willing to consider the difference between P and NP so don't sweat it

2) verify that 392321 is a factor of 123109824098231
Sure it's a little bit of nasty long division but you should be able to solve this in about a minute

This is possibly the simplest and clearest example of the difference between verifying and answering. The prime factorization of this number is 392321 * 313798711, so the only way you are going to factor it is by attempting thousands of divisions for prime numbers (there may be slightly faster algorithms but this is essentially as good as it gets)

These problems are not actually in P or NP because they aren't decision problems but you can convert this type of thing into a decision problem by tweaking the question a bit: does 123109824098231 have a factor which is smaller than 400000? The only way you can answer this is to try all the factorizations like when you were asked to find a factor, but once I say "try the number 392321", it's easy to check that the answer is yes.

This is also a good example of where if the answer is no it can be hard to prove... consider how you would convince me that 123109824098231 has no factors smaller than 300000 (for example, how would you prove that 392321 is prime and has no smaller factors? This is a hard question again)

 

[D H]

I don't understand here the difference between answering and verifying a problem in polynomial time. If we can verify that a yes-or-no problem is in NP in polynomial time, doesn't means that it can be answered?

First off, the oracle isn't just saying "yes". The oracle is saying "yes, because X". For example, consider the question "is there a way to assign values to the variables in a given boolean expression to make the expression true?" This is the satisfiability problem. Suppose the oracle answers "yes, because the expression is true when A is true, B is false, C is false, ...". Verifying whether the oracle truly did find an answer is just plug-and-chug. Doing what the oracle did is anything but plug-and-chug.

Second off, it's not just a matter of whether the question can be answered, period. The assumption is that the question can be answered. The issue here is a matter of speed. There are algorithms that do solve the satisfiability problem. None of these algorithms does so in polynomial time. The satisfiability algorithms instead take exponential time to find a solution to a given boolean expression.