5
$\begingroup$

Is there any problem such that its input size is N; its output size is polynomial in terms of N, yet its running time is super-polynomial(N) on a deterministic Turing machine?

Is there any problem such that its input size is N; its output size is polynomial in terms of N, yet its running time is super-polynomial(N) on a non-deterministic Turing machine?

Thanks!

EDIT:

The algorithm can use more than polynomial(N) space during computation.

The "polynomial(N) output size" was to avoid algorithms who generated output of size exp(N) and thus tribially taking atleast exp(N) time to run.

$\endgroup$
4
  • 1
    $\begingroup$ Recall that it's still open whether P is the same as PSPACE (problems which can be solved using polynomial amounts of memory but arbitrary time). So you'd need to find something that provably required super-polynomial amounts of space but didn't require super-polynomial amounts of space to give the output. $\endgroup$ Jul 14, 2010 at 5:39
  • $\begingroup$ Can you explain more? I think you're saying something deep, but I'm too stupid to understand. $\endgroup$ Jul 14, 2010 at 5:46
  • 3
    $\begingroup$ Do you need just EXPTime-Complete problem? If so there is one in wikipedia: en.wikipedia.org/wiki/EXPTIME. Given a (determinister for first question, nondeterministic for the second) Turing machine and time T decide wheter it halts after T steps. $\endgroup$
    – falagar
    Jul 14, 2010 at 6:10
  • 1
    $\begingroup$ You say that the output size is polynomial in N, but is this really what you mean? After all, any decision problem has yes/no output, which is constant size. So any decidable set that is not in P would be an example for your first question, and these are abundant. Similarly, any decidable set not in NP would be an example for your second. But perhaps you meant that the problem used only polynomial space altogether (putting it in PSPACE), rather than merely polynomial size output. $\endgroup$ Jul 14, 2010 at 10:30

3 Answers 3

18
$\begingroup$

Short answer: Yes and yes. For the first question, you could take any $EXPTIME$-complete problem. For the second you could take any $NEXPTIME$-complete problem.

Long answer:

Your first question is answered by the problem:

Given a deterministic Turing machine M, string x, and integer k in binary, does M accept x within k steps?

The output is one bit (yes or no). The above problem is $EXPTIME$-complete, hence it requires time that is exponential in the lengths of M, x, and k. It is crucial that k be written in binary. If it were written in unary (as a string of k ones) then it is solvable in polynomial time by direct simulation.

Your second question is answered by the problem:

Given a nondeterministic Turing machine N, string x, and integer k in binary, is there an accepting computation path in N(x) that has at most k steps?

Again the output is just one bit. The above problem is $NEXPTIME$-complete, and hence requires exponential time even on a nondeterministic machine. Again it is crucial that k is written in binary; if it were written in unary then the above problem is $NP$-complete, and is more commonly known as the "Bounded Halting Problem".

This can all be found in the early chapters of any text on complexity theory.

$\endgroup$
4
  • $\begingroup$ Oops... didn't realize that part of my answer was just repeating what others wrote (I just quickly typed in an answer and went on my way). Hope it helps, nevertheless $\endgroup$ Jul 14, 2010 at 7:28
  • $\begingroup$ @Ryan: basically because solving it any "faster" than simulating k steps, in the general case would be akin to solving the halting problem? $\endgroup$ Jul 14, 2010 at 18:15
  • $\begingroup$ @unknown: Yes, it is akin to solving the halting problem, in that from both assumptions you can derive a contradiction via diagonalization. The same proof strategy goes through with little modification. $\endgroup$ Jul 14, 2010 at 21:02
  • $\begingroup$ can someone elaborate on what the computation path means? like the decision the algorithm makes at each point of branching? $\endgroup$
    – Pita
    Sep 3, 2015 at 5:39
11
$\begingroup$

Remember that by the time hierarchy theorem we are assured that there is some decision problem (output size = 1) in EXP that is not in P. So the trivial answer to your question is YES. Of course, if you want a specific problem, then something EXP-complete as @falagar mentions will do it. if you want instead a 'natural problem', then I'm not sure what the answer is.

$\endgroup$
5
$\begingroup$

A number of EXPTIME-complete problems are listed here.

They include some interesting ones about games, such as generalized chess, checkers, and Go.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.