Return to Answer

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$. To keep this answer as simple as possible we will assume that $L$ is undecidable but this is not necessary; a language obtained by applying the Time Hierarchy Theorem to the Ackermann function would easily suffice). Assume that instances of $L$ can be padded, i.e., adding extra zeroes at the end does not change whether an instance is a yes- or no-instance. Starting with undecidable language $L'$, $L$ could be obtained by taking every string from $L'$ and appending a $1$ followed by an arbitrary amount of zeroes. Clearly $L$ is still undecidable.

Now consider the subset of $L$ containing only those strings whose length can be expressed as a tower of powers of two (i.e., $1, 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \ldots$). We split this subset into three languages $L_0, L_1, L_2$, depending on the height of the tower of powers of two. $L_0$ contains those strings where the tower has a height which is a multiple of $3$, $L_1$ contains strings whose height is $1$ modulo $3$, $L_2$ those strings whose height is $2$ modulo $3$.

Neither $L_0, L_1$ or $L_2$ are in $NP$. If they were, we could decide $L$ by padding instances to make their length the appropriate tower of powers of two, and then solving them using the $NP$ algorithm. Obviously the padding can increase the length of the instance exponentially, but if $L$ is sufficiently hard (e.g., undecidable) this does not matter.

Now, to answer the original question, can every problem in $NP$ be reduced in polynomial time to $L_0, L_1$ and $L_2$ (all of which are outside $NP$)? If we take some problem instance of a problem in $NP$, then at least one of the reductions (to $L_0, L_1$ or $L_2$) will result in an exponentially smaller instance. This is because the reduction, being polynomial, cannot increase the size of the instance too much, so (due to the large gaps in instance sizes) must - for at least one of $L_0, L_1$ or $L_2$ - give a much smaller instance as output.

Intuitively, this sounds very unlikely. It would mean we could take an arbitrary problem in $NP$ and in polynomial time output an exponentially smaller instance (albeit of a much harder problem).

Formally, this would mean that $NP\subseteq P/poly$, a consequence which is regarded as unlikely since it would imply the collapse of the polynomial hierarchy.

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$. To keep this answer as simple as possible we will assume that $L$ is undecidable but this is not necessary; a language obtained by applying the Time Hierarchy Theorem to the Ackermann function would easily suffice. Assume that instances of $L$ can be padded, i.e., adding extra zeroes at the end does not change whether an instance is a yes- or no-instance. Starting with undecidable language $L'$, $L$ could be obtained by taking every string from $L'$ and appending a $1$ followed by an arbitrary amount of zeroes. Clearly $L$ is still undecidable.

Now consider the subset of $L$ containing only those strings whose length can be expressed as a tower of powers of two (i.e., $1, 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \ldots$). We split this subset into three languages $L_0, L_1, L_2$, depending on the height of the tower of powers of two. $L_0$ contains those strings where the tower has a height which is a multiple of $3$, $L_1$ contains strings whose height is $1$ modulo $3$, $L_2$ those strings whose height is $2$ modulo $3$.

Neither $L_0, L_1$ or $L_2$ are in $NP$. If they were, we could decide $L$ by padding instances to make their length the appropriate tower of powers of two, and then solving them using the $NP$ algorithm. Obviously the padding can increase the length of the instance exponentially, but if $L$ is sufficiently hard (e.g., undecidable) this does not matter.

Now, to answer the original question, can every problem in $NP$ be reduced in polynomial time to $L_0, L_1$ and $L_2$ (all of which are outside $NP$)? If we take some problem instance of a problem in $NP$, then at least one of the reductions (to $L_0, L_1$ or $L_2$) will result in an exponentially smaller instance. This is because the reduction, being polynomial, cannot increase the size of the instance too much, so (due to the large gaps in instance sizes) must - for at least one of $L_0, L_1$ or $L_2$ - give a much smaller instance as output.

Intuitively, this sounds very unlikely. It would mean we could take an arbitrary problem in $NP$ and in polynomial time output an exponentially smaller instance (albeit of a much harder problem).

Formally, this would mean that $NP\subseteq P/poly$, a consequence which is regarded as unlikely since it would imply the collapse of the polynomial hierarchy.

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$. To keep this answer as simple as possible we will assume that $L$ is undecidable but this is not necessary; a language obtained by applying the Time Hierarchy Theorem to the Ackermann function would easily suffice). Assume that instances of $L$ can be padded, i.e., adding extra zeroes at the end does not change whether an instance is a yes- or no-instance. Starting with undecidable language $L'$, $L$ could be obtained by taking every string from $L'$ and appending a $1$ followed by an arbitrary amount of zeroes. Clearly $L$ is still undecidable.

Now consider the subset of $L$ containing only those strings whose length can be expressed as a tower of powers of two (i.e., $1, 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \ldots$). We split this subset into three languages $L_0, L_1, L_2$, depending on the height of the tower of powers of two. $L_0$ contains those strings where the tower has a height which is a multiple of $3$, $L_1$ contains strings whose height is $1$ modulo $3$, $L_2$ those strings whose height is $2$ modulo $3$.

Neither $L_0, L_1$ or $L_2$ are in $NP$. If they were, we could decide $L$ by padding instances to make their length the appropriate tower of powers of two, and then solving them using the NP algorithm. Obviously the padding can increase the length of the instance exponentially, but if $L$ is sufficiently hard (e.g., undecidable) this does not matter.

Now, to answer the original question, can every problem in $NP$ be reduced in polynomial time to $L_0, L_1$ and $L_2$ (all of which are outside $NP$)? If we take some problem instance of a problem in $NP$, then at least one of the reductions (to $L_0, L_1$ or $L_2$) will result in an exponentially smaller instance. This is because the reduction, being polynomial, cannot increase the size of the instance too much, so (due to the large gaps in instance sizes) must - for at least one of $L_0, L_1$ or $L_2$ - give a much smaller instance as output.

Intuitively, this sounds very unlikely. It would mean we could take an arbitrary problem in $NP$ and in polynomial time output an exponentially smaller instance (albeit of a much harder problem).

Formally, this would mean that $NP\subseteq P/poly$, a consequence which is regarded as unlikely since it would imply the collapse of the polynomial hierarchy.

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$. To keep this answer as simple as possible we will assume that $L$ is undecidable but this is not necessary; a language obtained by applying the Time Hierarchy Theorem to the Ackermann function would easily suffice). Assume that instances of $L$ can be padded, i.e., adding extra zeroes at the end does not change whether an instance is a yes- or no-instance. Starting with undecidable language $L'$, $L$ could be obtained by taking every string from $L'$ and appending a $1$ followed by an arbitrary amount of zeroes. Clearly $L$ is still undecidable.

Now consider the subset of $L$ containing only those strings whose length can be expressed as a tower of powers of two (i.e., $1, 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \ldots$). We split this subset into three languages $L_0, L_1, L_2$, depending on the height of the tower of powers of two. $L_0$ contains those strings where the tower has a height which is a multiple of $3$, $L_1$ contains strings whose height is $1$ modulo $3$, $L_2$ those strings whose height is $2$ modulo $3$.

Neither $L_0, L_1$ or $L_2$ are in $NP$. If they were, we could decide $L$ by padding instances to make their length the appropriate tower of powers of two, and then solving them using the $NP$ algorithm. Obviously the padding can increase the length of the instance exponentially, but if $L$ is sufficiently hard (e.g., undecidable) this does not matter.

Now, to answer the original question, can every problem in $NP$ be reduced in polynomial time to $L_0, L_1$ and $L_2$ (all of which are outside $NP$)? If we take some problem instance of a problem in $NP$, then at least one of the reductions (to $L_0, L_1$ or $L_2$) will result in an exponentially smaller instance. This is because the reduction, being polynomial, cannot increase the size of the instance too much, so (due to the large gaps in instance sizes) must - for at least one of $L_0, L_1$ or $L_2$ - give a much smaller instance as output.

Intuitively, this sounds very unlikely. It would mean we could take an arbitrary problem in $NP$ and in polynomial time output an exponentially smaller instance (albeit of a much harder problem).

Formally, this would mean that $NP\subseteq P/poly$, a consequence which is regarded as unlikely since it would imply the collapse of the polynomial hierarchy.

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.

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$. To keep this answer as simple as possible we will assume that $L$ is undecidable but this is not necessary; a language obtained by applying the Time Hierarchy Theorem to the Ackermann function would easily suffice). Assume that instances of $L$ can be padded, i.e., adding extra zeroes at the end does not change whether an instance is a yes- or no-instance. Starting with undecidable language $L'$, $L$ could be obtained by taking every string from $L'$ and appending a $1$ followed by an arbitrary amount of zeroes. Clearly $L$ is still undecidable.

Now consider the subset of $L$ containing only those strings whose length can be expressed as a tower of powers of two (i.e., $1, 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \ldots$). We split this subset into three languages $L_0, L_1, L_2$, depending on the height of the tower of powers of two. $L_0$ contains those strings where the tower has a height which is a multiple of $3$, $L_1$ contains strings whose height is $1$ modulo $3$, $L_2$ those strings whose height is $2$ modulo $3$.

Neither $L_0, L_1$ or $L_2$ are in $NP$. If they were, we could decide $L$ by padding instances to make their length the appropriate tower of powers of two, and then solving them using the NP algorithm. Obviously the padding can increase the length of the instance exponentially, but if $L$ is sufficiently hard (e.g., undecidable) this does not matter.

Now, to answer the original question, can every problem in $NP$ be reduced in polynomial time to $L_0, L_1$ and $L_2$ (all of which are outside $NP$)? If we take some problem instance of a problem in $NP$, then at least one of the reductions (to $L_0, L_1$ or $L_2$) will result in an exponentially smaller instance. This is because the reduction, being polynomial, cannot increase the size of the instance too much, so (due to the large gaps in instance sizes) must - for at least one of $L_0, L_1$ or $L_2$ - give a much smaller instance as output.

Intuitively, this sounds very unlikely. It would mean we could take an arbitrary problem in $NP$ and in polynomial time output an exponentially smaller instance (albeit of a much harder problem).

Formally, this would mean that $NP\subseteq P/poly$, a consequence which is regarded as unlikely since it would imply the collapse of the polynomial hierarchy.