patternMinor
What will happen to NP-Hard problems if P=NP
Viewed 0 times
whathardhappenwillproblems
Problem
I was going through the lecture of prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class.
He further said that if we can prove that there exists a problem that belongs to NP but not to P, then we can absolutely be sure that NP hard problems don't belong to P class.
Here is my question... What happens if P=NP. Thus it mean that all NP-hard problems become polynomially solvable? Will all NP hard problems reduce to polynomial order if P=NP?
He further said that if we can prove that there exists a problem that belongs to NP but not to P, then we can absolutely be sure that NP hard problems don't belong to P class.
Here is my question... What happens if P=NP. Thus it mean that all NP-hard problems become polynomially solvable? Will all NP hard problems reduce to polynomial order if P=NP?
Solution
No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in NP. Then these problems will not be polynomial time solvable regardless of whether or not P=NP.
Context
StackExchange Computer Science Q#99044, answer score: 8
Revisions (0)
No revisions yet.