4
$\begingroup$

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

$\endgroup$

migrated from cstheory.stackexchange.com Jun 10 '14 at 22:56

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 5
    $\begingroup$ $\{ \langle M, s, x \rangle \mid M \text{ accepts } x \text{ within } s \text{ steps}\}$ $\endgroup$ – GMB Jun 10 '14 at 3:18
  • $\begingroup$ @GMB: Assuming you can show that there is no faster way but simulating $M$ for $s$ steps. $\endgroup$ – Raphael Jun 11 '14 at 6:26
  • $\begingroup$ @Raphael - the language GMB have mentioned is known to be EXPTIME-complete. $\endgroup$ – R B Jun 11 '14 at 6:35
  • $\begingroup$ @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!". $\endgroup$ – Raphael Jun 11 '14 at 6:37
7
$\begingroup$

Every single-exponential (i.e. known to be solvable in $O(c^n)$ for some constant $c$) EXPTIME-complete problem will answer your requirements.

For example, see checking thorough re refinement on finite modal transition systems.

$\endgroup$
  • 2
    $\begingroup$ "solvable in ... for some constant $c$" $\: \mapsto \:$ "in E" $\;\;\;\;$ $\endgroup$ – user12859 Jun 10 '14 at 6:04
  • 1
    $\begingroup$ One should note that P $\subsetneq$ EXPTIME is known. $\endgroup$ – Raphael Jun 11 '14 at 6: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.