NP-hardness does not imply lower bound, strictly speaking?

Question

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.

Answer 1

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!).

Answer 2

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).