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., $\min(\vert c\vert,\vert x\vert)$.

  
  

• Bad News: NPO PB-complete [284].

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