Next: Formal Languages Up: Automata Theory Previous: LONGEST COMPUTATION Index

### SHORTEST COMPUTATION

- 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., .

- Bad News: NPO PB-complete [269].

- Comment: Variation in which the Turing machine is oblivious is also NPO PB-complete.