1
$\begingroup$
A problem is NP-hard iff every NP problem can be polynomially-time reduced to it.

Hardness is often intuitively explained as a lower bound. But it isn't, strictly speaking. For the sake of the argument, assume P=NP. Now the definition becomes:

A problem is P-hard iff every P problem can be polynomially-time reduced to it.

Because the above definition uses the polynomial-time reduction, the overall running time is polynomial (reduction + solving the resulting problem), no matter how easy is the resulting problem. Hence we could get an absurd result: a problem, which runs in constant time (hence lower bound is constant), is P-hard.

The definition makes total sense if we assume that NP>P. Do people assume NP>P?

The same question arises for the definition of PSPACE-hardness, where book authors use polynomial-time reduction, rather than something strictly easier than PSPACE.

I guess the answer to this question is simply "yes", sorry for the rant.

$\endgroup$
1
$\begingroup$

Hardness is often intuitively explained as a lower bound.

In general, "hardness results" obtained by reductions yield a conditional lower bound that relies on assuming a sort of lower bound on a single problem. In the case of NP-hardness, the following statement is true:

assuming P$\neq$NP, NP-hard problems cannot be solved in polynomial time

P$\neq$NP is equivalent to 3SAT (or any other NP-complete problem) not being solvable in polynomial time, so we can equivalently say

assuming 3SAT cannot be solved in polynomial time, NP-hard problems cannot be solved in polynomial time

The theory of NP-hardness and the 'belief' P$\neq$NP that has become "common" enough that the required assumption is often not made explicit. Unfortunately, no-one has been able to actually prove the assumption (and almost no-one expects that to happen any time soon)


Note that this means that if we can actually prove a lower bound for a single problem, reductions can give an unconditional result. For example, we know that EXPTIME-complete problems cannot be solved in polynomial time. This means that if a problem is EXPTIME-hard, it cannot be solved in polynomial time (without needing any further assumptions!).

$\endgroup$
1
$\begingroup$

Yes, if P = NP then any decision problem is NP hard as long as there is one problem instance where the answer is "YES" and one where the answer is "NO".

Just check the definition of NP-hard (and check why problems where every instance has the answer YES or every instance has the answer NO are not NP-hard by that definition).

$\endgroup$
  • $\begingroup$ thanks, got it. For the first task, the reductor solves a given NP-problem instance and then: if the answer is YES, it creates the YES-instance of the target problem, otherwise it creates the NO-instance. Such a reductor is polynomial-time, because (1) we assumed that P=NP and (2) the size of YES- and NO-instances does not depend on the input size. The second task: a "valid" problem cannot be NP-hard, because there are NP problems that contain YES and NO instances. In fact, no "valid" problem can be X-hard, for any X... $\endgroup$ – Ayrat Jan 19 '19 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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