Register to reply 
NP vs P  difference between veryfing and answering 
Share this thread: 
#1
Apr2912, 08:35 AM

P: 81

Hi,
1. A yesorno problem is in P (Poynomial time) if it the answer can be computed in polynomial time. 2 A yesorno problem is in NP (Nondeterministic 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 yesorno problem is in NP in polynomial time, doesn't means that it can be answered? 


#2
Apr2912, 12:10 PM

P: 169

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. 


#3
Apr2912, 12:20 PM

P: 800

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. 


#4
Apr2912, 12:28 PM

Emeritus
Sci Advisor
PF Gold
P: 4,500

NP vs P  difference between veryfing and answering
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) 


#5
Apr2912, 02:14 PM

Mentor
P: 15,202

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. 


Register to reply 
Related Discussions  
Veryfing ODE for complicated y(t)  Calculus & Beyond Homework  4  
Veryfing Green theorem  Calculus & Beyond Homework  1  
Need some help answering this problem thanks  Introductory Physics Homework  2  
Need help veryfing E&M Multiple Choice  Introductory Physics Homework  0  
Answering Your Own Questions  General Discussion  7 