Next:
AL3 SHORTEST COMPUTATION
Up:
Automata Theory
Previous:
AL1 MINIMUM CONSISTENT
-
I
NSTANCE
:
Nondeterministic Turing machine
M
, binary input string
x
.
-
S
OLUTION
:
Nondeterministic guess string
c
produced by
M
on input
x
.
-
M
EASURE
:
The length of the shortest of the strings
c
and
x
, i.e.,
.
-
Bad News:
NPO PB-complete [
49
].
-
Comment:
Variation in which the Turing machine is oblivious is also NPO PB-complete.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997