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.



EXPTime algorithms
**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.


