If a problem is not in NP, prove that every NP problem can be efficiently reduced to it

Question

I understand that an NP-hard problem is a problem X such that any problem in NP can be reduced to X in polynomial time.

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? If not, what is the proof that if I can efficiently solve a problem that is strictly not in NP, then I can efficiently solve every problem in NP?

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?

Note: The linked question asks the converse problem - does there exist a problem outside NP that cannot be reduced to a problem in NP. Indeed there are, for example the "(Non-)equivalence of two regular expressions" problem. However, from my understanding, every problem in NP can be reduced to this problem in polynomial time. Please correct me if I have misunderstood.

Answer 1

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.

Answer 2

Hartmanis et al proved that there are sparse set in $PSPACE\backslash NP$ iff $EXPSPACE \neq NEXPTIME$ and it is highly believed they are correct. This sparse set is not in NP and is not NP-hard because it is sparse.

Sparse language: In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n.

Mahaney's theorem is a theorem in computational complexity theory proven by Stephen Mahaney that states that if any sparse language is NP-Complete, then P=NP. The proof idea is easy. Take SAT which is np-compelete and suppose for the sake of contradiction there exists a sparse np-complete language S. Now solve the SAT‌ instance via self reduction mapping tree for example you want to solve $\phi (x_1,x_2,...,x_n)$ convert this formula to $\phi (x_1=T,x_2,...,x_n)\land \phi (x_1=F,x_2,...,x_n)$ and solve this new formula as. Repeating this argument makes exponentially tree for formula but we know that SAT‌ is polynomially reducible to S which is sparse, you can use this fact to pruning the self reduction tree to keep the size of the tree bounded in a polynomial and solving sat with a polynomial algorithm. For the detail of manhaney's theorem you can read manhaney's proof, it is easy to find other resources for proof just google it.

To complete our proof we need last theorem which states there are sparse set in $PSPACE-NP$ if $EXPSPACE‌ \neq NEXPTIME$.(even you can replace nexptime with np in this case. We don't need other direction!)

proof. If $EXPSPACE \neq NEXPTIME$ then we may assume that there exists a set $A, A \subseteq \{0,1\}^*$, st $A\in PSPACE-NEXPTIME$ if we prefix each string in A by a 1 and interpret these strings as binary representation of integers, then we can convert A to tally(a language is tally if its member are like $1^n$) notaion:

$TALLY(A)=\{1^n:n \in 1A\}$.

since $A$ is in $PSPACE$ and not in $NEXPTIME$ then $TALLY(A)\in PSPACE‌-NP$ and it is sparse by the definition so by manhaney's theorem and the fact $p \neq np$ it is not np-hard .

It is unlikely for the Manhaney's theorem and $EXPSPACE=NEXPTIME‌$ to be true so the language you are looking for is $TALLY(A)$.

Answer 3

See the following Wikipedia article, notably the section on exptime complete problems: https://en.m.wikipedia.org/wiki/EXPTIME

Correction: EXPSPACE-complete problems will do the job. For example, the equivalence problem for regular expressions with squaring. There is a classic TCS paper by Albert Meyer and Larry Stockmeyer from 1972 proving that this is EXPSPACE-complete.