Are there any proofs of exponential lower bound time complexity

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.

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.

StackExchange Computer Science Q#117302, answer score: 9