EXPTime algorithms - MathOverflow

EXPTime algorithms

2010-07-14T05:18:18Z

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.

Answer by Suresh Venkat for EXPTime algorithms

2010-07-14T06:20:27Z

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.

Answer by Ryan Williams for EXPTime algorithms

2010-07-14T06:40:52Z

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.

Answer by John Stillwell for EXPTime algorithms

2010-07-14T10:32:18Z

A number of EXPTIME-complete problems are listed here.

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