1
$\begingroup$

My question is that if P = NP, then we can solve any NP-hard problems (the one which is NP-complete and the one which is not-NP-complete) by saying that since we have a polynomial time algorithm to solve the NP problems and since the reduction works in polynomial time. Therefore, polynomial to polynomial is polynomial, and so we can solve any NP-hardness problem. For example, we can solve the TSP by calling to an NP-complete problem which have polynomial time since P=NP, and since the reduction is polynomial time, therefore we can solve TSP in polynomial time.

How could disprove this argument? What is the clue to say that NP-hardness(the one which doesn't intersect with NP-complete) can not be solved in polynomial time even if P=NP.

I know that if P = NP, then we can only solve any problem in NP (but not in NP-hard). But I want to know what it makes NP-hard (the one that have no intersection with NP-complete) is not solvable in polynomial time even if P=NP since we have polynomial time reduction and polynomial time algorithm given P=NP.

Thank you

Improve this question
$\endgroup$
3
  • $\begingroup$ I think in the first paragraph you mean "NP-complete". The sentence " if P = NP, then we can solve any NP-hard problems" is wrong, otherwise. Maybe your actual question is "can you show me a NP-hard problem, which we already know not to belong to P?" $\endgroup$
    – chi
    Commented Feb 25, 2017 at 12:14
  • $\begingroup$ You're right, but I mean to use NP-hardness because I want to find a clue which fails this statement. I'm trying to find a clue where if someone give an argument as in above saying we have P=NP, and we have polynomial reduction, therefore why not having NP-hard (the one that doesn't intersect with NP-complete) to have a polynomial time $\endgroup$
    – YOUSEFY
    Commented Feb 25, 2017 at 12:16
  • $\begingroup$ NP-hardness makes sense for the last part of the question, but not for the first, which IMO only causes confusion since you start from wrong premises. $\endgroup$
    – chi
    Commented Feb 25, 2017 at 12:17

2 Answers 2

Reset to default
2
$\begingroup$

You have your reductions the wrong way around. A problem $X$ is NP-hard if every problem in NP can be reduced to $X$. That is, saying that $X$ is NP-hard means that, if we had an efficient algorithm for $X$, we would have an efficient algorithm for every problem in NP: $X$ is easy implies all of NP is easy.

So, suppose that P$\,=\,$NP. Then, all of NP is easy, but that tells us nothing about $X$, because the implication goes the wrong way. Maybe $X$ is easy; maybe it's hard. In fact, some NP-hard problems are definitely hard: the halting problem is NP-hard but it's undecidable, regardless of what the relationship between P and NP turns out to be.

Improve this answer
$\endgroup$
8
  • $\begingroup$ if P=NP, then all of NP is easy, and since the reduction is also easy. Why not TSP (which is NP-hard) is also easy?! What I'm saying is TSP lies in NP-hard, then after P=NP? we claim that TSP cannot be solved in polynomial time! Why? because P=NP only solves NP problems. Now after NP=P, for example TSP we have an easy algorithm (since P=NP) and an easy reduction. So, where is the wrong?! Why not solve TSP in polynomial time after claiming that P=NP!! I know some NP-hard problems such as halting problem cannot be easy even after P=NP, but what about TSP and alike?!! $\endgroup$
    – YOUSEFY
    Commented Feb 25, 2017 at 13:17
  • $\begingroup$ if no one has said about this, then there must be a class of problems that would contain a set of problems that are neither in NP nor in NP-complete but it is in NP-hard and if P=NP, then this class of problems will be broken to be equal to NP=P=NP-complete. $\endgroup$
    – YOUSEFY
    Commented Feb 25, 2017 at 13:25
  • $\begingroup$ "If P = NP, then all of NP is easy" - not at all. Anything taking say $O (n^{12})$ operations is not solvable for more than moderate problem sizes. And NP hard problems are mostly problems that are not in NP, so P = NP says nothing at all about NP-hard problems. $\endgroup$
    – gnasher729
    Commented Feb 25, 2017 at 14:54
  • 1
    $\begingroup$ @gnasher729 The conventional meaning of "easy" is "in P". That may not be a particularly practical definition of "easiness" but it's the one that everybody uses. I really don't understand your second sentence because my answer already explains why P=NP has no consequences for NP-hard problems that aren't NP-complete, and I give the halting problem as an example. $\endgroup$
    – David Richerby
    Commented Feb 25, 2017 at 15:40
  • $\begingroup$ @YOUSEFY TSP is NP-complete so it's easy if P=NP. I don't understand your second comment at all. $\endgroup$
    – David Richerby
    Commented Feb 25, 2017 at 15:42
0
$\begingroup$

I suppose one could potentially "disprove" that argument by proving P=NP,
since as David mentions, the halting problem is NP-hard and undecidable.



Your argument is like

If Goldbach's conjecture is true then

we can fit (10^(10^100))+1 items into 10^(10^100) holes
without any hole having more than one item

by saying that since 10^(10^100) is a sum of two primes and since the primes are odd.

:


Namely, ​ "we have a polynomial time algorithm to solve the NP problems and"
"the reduction works in polynomial time" ​ follow from your assumption,
but your attempted conclusion simply does not follow from ​ "we have a polynomial time
algorithm to solve the NP problems and" "the reduction works in polynomial time" .

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.