Are there any proofs of exponential lower bound time complexity

Question

I'm trying to understand what are the techniques to prove an exponential time lower bound.

For some problems, we can prove that the size of the output is exponential is the size of the input, thus it takes an exponential number of steps just to write the output. For example for some generalized board games, if the input is the size of the board and the output is the sequence of winning steps.

But what about decision problems, where $|output|=1$ ? Are there any decision problems in $EXPTIME$ with known exponential lower-bounds ?

I don't see how we can prove such a lower bound. Like if we take again the generalized board game and ask the question if there is a winning strategy, we can prove that evaluating all strategies will take (in the worst case) exponential time, but how can we prove that evaluating all strategies is the only way to answer the question ?

Or if I take another example, if my input is a number $x$ and the output is $1$ iff there exist a permutation $p$ such as shuffling the bits of $x$ makes it prime, i.e. $p(x)$ is prime. Exhaustively exploring all permutations and running a primality test will probably be exponential in $|x|$, but what if there is a smart way to answer just by looking at $x$ (in sub-exponential time) ?

I hope that looking at an example of such a proof will help me grasp the principles involved.

Answer 1

The Time Hierarchy Theorem states that for any (reasonable) function $f$, there exists a problem that cannot be solved in time substantially faster than $f(n)$. The proof of this is similar to the proof of the undecidability of the Halting problem: we construct the decision problem "given a description of a Turing machine, does it halt in time at most $f(n)$ and then show that it cannot be decided substantially faster than $f(n)$, in a very similar way to showing that "does this Turing machine halt in finite time" cannot be decided (in finite time).

In the case of generalized board games (e.g., Chess), these are often $EXPTIME$-complete. This means any problem in $EXPTIME$ can be reduced in polynomial time to it. Since (by the Time Hierarchy Theorem) there are problems in $EXPTIME$ that cannot be solved in subexponential time, neither can Chess (or any other $EXPTIME$-complete problem).

Your other example (shuffling bits to get a prime number) probably doesn't require exponential time. The chance that a random permutation of the bits results in a prime is quite high, and only a polynomial number of guesses would be required to find a prime. The problem is in $NP$, so a proof that it requires exponential time would be a somewhat significant breakthrough.

Answer 2

Regarding the specific problem you pose about whether the bit of a number can be permuted to give a prime, I believe the following to be an algorithm in P.

If the number has fewer than 100 zeros in it or fewer than 100 ones in it, enumerate all permutations and test them all for primality using a primality test (e.g. AKS) and output accordingly. Otherwise output 1.

The correctness of this algorithm rests on the assumption that no number containing 100 ones and 100 zeros can't be rearranged into a prime. To see this heuristically, if $n$ is the number of ones and $m$ the number of zeros note that there are on the order of $(n+m)^{\min(n,m)}$ premutations and that $1$ in $\log(m+n)$ of them "should" be prime. Even summing over all $n,m>99$, it seems very unlikely that there is an exception to this assumption.

That it is polynomial time follows from the fact that if $n<100$ or $m<100$ then the number of permutations is at most $(n+m)^{99}$ and each can be tested in polynomial time using AKS.