Question

Professor Amongus has just designed an algorithm that can take any graph G with n vertices and determine in O(n^k) time whether G contains a clique of size k. Does Professor Amongus deserve the Turing Award for having just shown that P = NP? Why or why not?

R-17.12 Professor Amongus has just designed an algorithm that can take any graph G with n vertices and determine in O(nk) time whether G contains a clique of size k. Does Professor Amongus deserve the Turing Award for having just shown that P NP? Why or why not?

Answer 1

Yes definitely he deserves that award if he has solved that P = NP problem because it's not a just thing.Many researchers are chasing for that and if he is the one who stands out by proving that solution then its a remarkable success for all of us.

A proof that P = NP could have stunning practical consequences if the proof leads to efficient methods for solving some of the important problems in NP. It is also possible that a proof would not lead directly to efficient methods, perhaps if the proof is non-constructive, or the size of the bounding polynomial is too big to be efficient in practice. The consequences, both positive and negative, arise since various NP-complete problems are fundamental in many fields

Cryptographic hashing as the problem of finding a pre-image that hashes to a given value must be difficult in order to be useful, and ideally should require exponential time. However, if P=NP, then finding a pre-image M can be done in polynomial time, through reduction to SAT

Similarly, Stephen Cook says it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems

Hope this solved your query and I wish we can bring out best of this research as it is a remarkable one for all of us.