Skip to main content
2 of 5
added 16 characters in body
Tom van der Zanden
  • 13.4k
  • 1
  • 37
  • 55

I suppose an analogous question can also be asked for P and NP. If a problem is in NP, then can every problem in P be reduced in polynomial time to it?

No. There is a stupidly simple argument here: the empty language (i.e., a problem with no yes-instances) is in NP, but no problem in P can be reduced to it.

Does there exist a problem that is hard to solve but problems in NP cannot be reduced to it in polynomial time i.e. it does not satisfy the definition of NP-hard but is strictly not in NP?

Yes (conditional on some complexity theory assumptions). Let's take some stupidly hard problem $L$ that cannot be solved faster than (say) $2^{2^{2^{2^{2^n}}}}$ time (by the time hierarchy theorem, such problems exist). Assume that the problem allows instances to be padded (i.e., appending extra 0's at the end of an instance does not change whether it is a yes- or no-instance).

Let's now modify that problem so that only instances whose (bit-)length can be expressed as $2^{2^{2^{2k}}}$ are yes-instances (call the thus-obtained problem $L_1$). This problem is not in NP because otherwise we would have a $2^{poly(2^{2^{2^{2n}}})}$-time algorithm for the original problem (take an instance of $L$, pad it to obtain an instance of $L_1$, solve using the hypothetical NP algorithm).

Similarly, create problem $L_2$ whose instances are of size $2^{2^{2^{2k+1}}}$.

Suppose for any problem $A$ in $NP$, there was a polynomial reduction to both $L_1$ and $L_2$. At least one of these reductions will result in an exponentially smaller instance of either $L_1$ or $L_2$. This instance could then be solved with polynomial advice, and thus $NP\subseteq P/ poly$, a consequence that is regarded as unlikely as it implies the collapse of the polynomial hierarchy.

Tom van der Zanden
  • 13.4k
  • 1
  • 37
  • 55