This version of halting problem is with a flat distribution.
DISTRIBUTIONAL HALTING PROBLEM (VERSION 2)
Instance. Binary strings 
, 
, and 
, where
is a positive integer. The size of
the instance is 
.
Question. Does 
accept within 
steps?
Distribution. Randomly select binary strings , , and
with respect to the default uniform distribution. Hence,
the probability distribution is proportional to
,
where 
, 
, and 
.
This version of the distributional halting problem was first shown to be
average-case NP-complete by Gurevich [Gur91]. Randomized
reductions are used to handle the ``flatness.''
The version presented is from [Wan96].