The question of whether P=NP is perhaps the most famous in all of Computer Science. What does it mean? And why is it so interesting? Oh, and for extra credit, please post a proof of the statement's truth or falsehood. :) ...
Would it be an polynomial time algorithm to a specific NP-complete problem, or just abstract reasonings that demonstrate solutions to NP-complete problems exist? It seems that the a specific algoithm is much more helpful. With it, all we'll have to do to polynomially solve an NP problem is to convert it into the specific NP-complete p...
What are the differences between NP vs NP-Complete vs NP-Hard ? I am aware of many resources all over the web. I d like to read your explanations, and the reason is they might be different then what s out there, or it s out there and i m not aware. ...
I tried to recover a password. When thinking of this I recognized that the problem "password recovery" is a very nice example of a NP problem. If you know the password it's very easy to verify it in polynomial time. BUT if you don't know the password you have to search the whole space of possible solutions which can be shown to take expo...
What is the best book for a student learning about concepts such as NP-hard, NP-complete and P=?NP? I've already got the CLR but it doesn't really cover these particular topics as thoroughly. ...
Hello everybody, I know that P=NP has not been solved up to now, but can anybody tell me something about the following: What are currently the most promising mathematical / computer scientific methods that could be helpful to tackle this problem? Or are there even none such methods known to be potentially helpful up to now? Is there any...
Recently there has been a paper floating around by Vinay Deolalikar at HP Labs which claims to have proved that P != NP. Could someone explain how this proof works for us less mathematically inclined people? ...
I read the article on wikipedia but could not understand what exactly are NP problems. Can anyone tell me about them and also what is relation of them with P Problems? ...
Really.. I'm having the last test for graduation this Tuesday, and that's one of the things I just never could understand. I realize that a solution for NP problem can be verfied in polynomial time. But what does determinism has to do with that? And if you could explain me where NP-complete and NP-hard got their names, that would be grea...
From my understanding, all NP-complete problems are NP-hard but some NP-hard problems are known not to be NP-complete, and NP-hard problems are at least as hard as NP-complete problems. Is that mean NP-hard problems that are not NP-complete are harder? And how it is harder? ...