LONGEST COMPUTATION

Next: SHORTEST COMPUTATION Up: Automata Theory Previous: MINIMUM CONSISTENT FINITE AUTOMATON Index

INSTANCE: Nondeterministic Turing machine M, binary input string x.
SOLUTION: Nondeterministic guess string c produced by M on input x.
MEASURE: The length of the shortest of the strings c and x, i.e., $\min(\vert c\vert,\vert x\vert)$ .
Bad News: NPO PB-complete [77].
Comment: Variation in which the Turing machine is oblivious is also NPO PB-complete.

Viggo Kann
2000-03-20