Venkatesan and Rajagopalan [VR92] showed that
the distributional matrix representability problem is complete
for DistNP by reducing the distributional Post correspondence problem
to it under a randomized reduction.
They also
attempted to show that the bounded version of Diophantine
problem is average-case NP-complete. Their approach, however, depends
on a number theoretic conjecture that remains unproven.
The unbounded version of the Diophantine problem
is essentially Hilbert's tenth problem, which was shown to be
undecidable by Matijasevic [Mat70] based on the work of
Davis, Putnam, and Robinson [DPR61]. (A simplified proof
of this result can be found from [JM91]).
The bounded version of the Diophantine problem
has been studied by Adleman and Manders [AM76]
[AM75]
[MA78].
DISTRIBUTIONAL DIOPHANTINE PROBLEMS
Instance. A positive integers 
, 
, and an
integer polynomial 
of degree with variables,
where 
is a free term.
Question. Do there exist non-negative integers 
such that 
for 
, and
?
Distribution. First randomly choose polynomial 
and then
randomly and independently choose
with respect to the default random
distributions. The polynomial may be chosen with any
samplable distribution in which every polynomial has a
non-zero probability.
Showing that the distributional Diophantine problem is
average-case NP-complete is a challenging task, which
may require a deeper understanding of number theory.
We can see that almost all the average-case NP-complete
problems known so far
are bounded versions of some classical undecidable problems
except for the distributional graph edge coloring problem and
the distributional matrix transformation problem.
The task of bounding a witness size to put a problem in
NP is not always trivial. A well-known example is the proof
of 
[Pra75]. It is interesting
to note that
the use of randomized reductions has opened a door for us
to find average-case NP-complete problems
that do not belong to such kind of bounded
problems.
It is an important and challenging task to systematically investigate the average-case complexity of the NP-complete problems listed in [Kar72], and in [GJ79] at large. Some of these problems have been shown easy on average, but many of them remain unknown. Reductions will certainly play an important role in this investigation. In particular, randomized reductions will be a powerful tool to show that a distributional problem is average-case NP-complete since flat distributions come quite naturally to many of these problems.
Acknowledgment. I am grateful to Jay Belanger and Yuri Gurevich for reading an early version of this paper and I thank them for their helpful comments.
