Let 
be a fixed enumeration of
nondeterministic Turing machines in which the index
is an integer that codes up the symbols, states, and
transition table of the -th Turing machine 
.
DISTRIBUTIONAL HALTING PROBLEM (VERSION 1)
Instance. Binary strings , 
, and a positive integer
, where is a positive integer in binary form.
The size of the instance is 
.
Question. Does accept within steps?
Distribution. Proportional to
, where 
and 
.
This corresponds to the following
experiment: Randomly and independently
choose binary strings , , and a
positive integer
with respect to the default uniform distributions.
The distributional halting problem was shown
by Gurevich [Gur91]
to be average-case NP-complete. The version
presented here is from
[BCGL92]
[WB93a].