Next: Formal Languages
Up: Automata Theory
Previous: LONGEST COMPUTATION
Nondeterministic Turing machine M, binary input string x.
Nondeterministic guess string c produced by M on input x.
The length of the shortest of the strings c and x, i.e.,
- Bad News:
NPO PB-complete .
Variation in which the Turing machine is oblivious is also NPO PB-complete.