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$ 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$ 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$ 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$ 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$ 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$ 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$ 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$ 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$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.