# Unary in $P$, binary not in $P$

I would like to know if there is a known decision problem with the following characteristics:

• Represented in unary, the problem is decidable in polynomial time.
• Represented in binary, the problem is not decidable in polynomial time (and this fact has been proved, not just conjectured).

For example, Subset-Sum is in $P$ when represented in unary, but it is $NP$-complete in binary. However, this problem does not satisfy my second requirement because we do not know whether $P=NP$.

• $\{ \langle M, s, x \rangle \mid M \text{ accepts } x \text{ within } s \text{ steps}\}$ – GMB Jun 10 '14 at 3:18
• @GMB: Assuming you can show that there is no faster way but simulating $M$ for $s$ steps. – Raphael Jun 11 '14 at 6:26
• @Raphael - the language GMB have mentioned is known to be EXPTIME-complete. – R B Jun 11 '14 at 6:35
• @RB: Ah, that's important to note then. Too many beginners fall into the trap of thinking along the lines of "I can't find a better algorithm, therefore there is none!". – Raphael Jun 11 '14 at 6:37

Every single-exponential (i.e. known to be solvable in $O(c^n)$ for some constant $c$) EXPTIME-complete problem will answer your requirements.
• "solvable in ... for some constant $c$" $\: \mapsto \:$ "in E" $\;\;\;\;$ – user12859 Jun 10 '14 at 6:04
• One should note that P $\subsetneq$ EXPTIME is known. – Raphael Jun 11 '14 at 6:38