EXPTime algorithms - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T19:12:27Z http://mathoverflow.net/feeds/question/31796 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31796/exptime-algorithms EXPTime algorithms LowerBounds 2010-07-14T05:18:18Z 2010-07-14T18:14:08Z <p>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?</p> <p>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?</p> <p>Thanks!</p> <p>EDIT:</p> <p>The algorithm can use more than polynomial(N) space during computation.</p> <p>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.</p> http://mathoverflow.net/questions/31796/exptime-algorithms/31801#31801 Answer by Suresh Venkat for EXPTime algorithms Suresh Venkat 2010-07-14T06:20:27Z 2010-07-14T06:20:27Z <p>Remember that by the <a href="http://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="nofollow">time hierarchy theorem</a> 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. </p> http://mathoverflow.net/questions/31796/exptime-algorithms/31805#31805 Answer by Ryan Williams for EXPTime algorithms Ryan Williams 2010-07-14T06:40:52Z 2010-07-14T06:40:52Z <p><strong>Short answer:</strong> Yes and yes. For the first question, you could take any \$EXPTIME\$-complete problem. For the second you could take any \$NEXPTIME\$-complete problem.</p> <p><strong>Long answer:</strong> </p> <p>Your first question is answered by the problem:</p> <p><em>Given a deterministic Turing machine M, string x, and integer k in binary, does M accept x within k steps?</em></p> <p>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. </p> <p>Your second question is answered by the problem:</p> <p><em>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?</em></p> <p>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". </p> <p>This can all be found in the early chapters of any text on complexity theory.</p> http://mathoverflow.net/questions/31796/exptime-algorithms/31828#31828 Answer by John Stillwell for EXPTime algorithms John Stillwell 2010-07-14T10:32:18Z 2010-07-14T10:32:18Z <p>A number of EXPTIME-complete problems are listed <a href="http://en.wikipedia.org/wiki/EXPTIME" rel="nofollow">here</a>.</p> <p>They include some interesting ones about games, such as generalized chess, checkers, and Go.</p>