It is a popular open question if there is a problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH. I recommend reading that question first. That question states that, assuming the ETH (Exponential Time Hypothesis), we know problems that cannot be solved in time something like $2^{o(n/\log n)}$ (namely, 3-SAT) and then proceeds to ask if we then also know problems that cannot be solved in time $2^{o(n)}$. Remember that little-oh notation is used here: $o(f(n))$ might be read as "strictly faster than $O(f(n))$".

Under some assumptions$^{(A)}$ (such as that the proof must effectively use the ETH and not "just" prove something stronger), I naively expect that settling that question by finding such a problem immediately provides a way to represent (an NP-complete subset of) 3-SAT instances in $O(n)$ bits, where $n$ is the number of variables. If this were true though, that question would be nothing else than asking if it is the case that we can represent 3-SAT instances in a number of bits that's linear in the number of variables (regardless of the outcome of that question). So my question really is, how could the referenced question be settled without answering this question about 3-SAT? How are the two questions different?

The reasoning is as follows. The definition of ETH involves 3-SAT. So the most straightforward way to show that some problem $B$ cannot be solved in $o(2^n)$ under ETH starts out by reducing 3-SAT to $B$. If this reduction involves an increase (or no decrease) in the input size as is the case with most NPC-reductions, this will not get us closer to proving $2^{o(n)}$ for the new problem is impossible. On the other hand, if it does involve a large-enough decrease in the input size, the new input is a representation of the original 3-SAT problem in $O(n)$ bits, where $n$ is the number of variables. (I think this assumes under the assumptions $(A)$ that the reduction from 3-SAT to $B$ is invertible).

If this rules out the possibility of reductions, what types of proof do we have left? It feels like trying to prove NP-hardness for a problem when we have already ruled out the possibility of reducing 3-SAT to it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.