4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Raphael that question is different from mine as far as I can tell. The question there asks for a problem which is NP-hard but not in NP. I'm asking for a problem X that is not in NP but also not NP-hard i.e. problems in NP cannot be reduced to X in polynomial time. Alternatively, if such an X does not exist, how does one prove that? $\endgroup$ – user1936752 Oct 24 at 0:13
  • $\begingroup$ I suggest taking another look. That duplicate gives examples of problems that meet your conditions (the problems are hard to solve but cannot be reduced in polynomial time to a NP problem). Beware that "cannot be reduced in polynomial time to an NP problem" is not the same as "not NP-hard". $\endgroup$ – D.W. Oct 24 at 3:32
  • $\begingroup$ @D.W. sorry, if I'm being obtuse but I think they are different or I have a fundamental misunderstanding. I realize my original question was written incorrectly and I have edited but my comment above is correct. The difference is the following: The duplicate asks about the existence of a problem not in NP that cannot be reduced to an NP problem. I'm asking about the existence of a problem not in NP such that not every NP problem can be reduced to it. Am I making sense? $\endgroup$ – user1936752 Oct 24 at 11:02
  • $\begingroup$ My fault, I misunderstood. You absolutely are making sense. Thank you for editing and explaining. $\endgroup$ – D.W. Oct 24 at 18:01
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How you can prove that $L_1$ is not in NP? The restriction on L could reduce the complexity such that $L_1 \in NP$ or even $L_1=empty$. Your argument "otherwise we would have a $2^{poly(2^{2^{2n}})}$" have some errors because the restricted version of L may be in very smaller class than the class of L. You force the language to be sparse and it is not work in the scence you want. It is not complete for me. $\endgroup$ – Mohsen Ghorbani Oct 24 at 22:41
  • $\begingroup$ $L_1$ cannot be empty because of the assumption that instances can be padded. More formally, we can define that $L_1$ is obtained by taking every string in $L$, appending a $1$ to it, then appending enough $0$'s to bring the length up to $2^{2^{2k}}$ (for some $k$). If the resulting $L_1\in NP$, we could use it to solve problems from $L$ faster: take some instance of $L$, pad it in the same way as we did before, then solve it using the hypothetical $NP$ algorithm. If we start with a string of length $n$, then the resulting padded string will certainly be shorter than $2^{2^{2(n+1)}}$. $\endgroup$ – Tom van der Zanden Oct 25 at 7:45
  • 1
    $\begingroup$ It turned out that we need the instance lengths to be arbitrary powers of two rather than n-times exponential. I updated the answer the reflect this. $\endgroup$ – Tom van der Zanden Oct 25 at 9:21
  • 1
    $\begingroup$ @user1936752 1) Not with my construction. The choice to pad with zeroes is arbitrary (we could pad with anything else), but we need to be able to differentiate the padding from the original instance. From an instance of $L$ we can recover the original instance by dropping all trailing zeroes and then removing the $1$ at the end. $\endgroup$ – Tom van der Zanden Oct 25 at 13:27
  • 1
    $\begingroup$ @user1936752 2) The padding is irrelevant to the size difference. The padding argument is only relevant to establish the hardness of $L_0, L_1, L_2$. The point is that the sizes of the instances of $L_i$ are spaced exponentially far apart. A reduction, if presented with an input that is "in the middle" of instances sizes, must give a much smaller instance as output because a larger instance is too large (not polynomial in the original length). $\endgroup$ – Tom van der Zanden Oct 25 at 13:31
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the reference. I'm afraid I don't have much of a background in complexity theory so would you be able to explain a little bit what the idea behind your argument is? Thanks! $\endgroup$ – user1936752 Oct 25 at 0:04
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It is possible that EXPTIME=NP so this does not fully answer the question. $\endgroup$ – Tom van der Zanden Oct 23 at 21:06
  • $\begingroup$ Ah, thanks. It was EXPSPACE what I had in mind. That is provably different from PSPACE and thus from NP because of the space hierarchy theorem. $\endgroup$ – Hermann Gruber Oct 24 at 15: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.