We consider square matrices with integer entries.
The matrix representability problem is to decide, for a given
matrix 
and a set of matrices 
, whether
can be expressed as a product of matrices in 
.
This problem was shown to be undecidable for 
matrices
by Markov [Mar54] and was later improved to 
matrices [Mar58]. Venkatesan and Rajagopalan [VR92]
considered bounded version of this problem for 
matrices as follows. The size of a matrix 
,
denoted by
, is equal to 
,
where 
is in binary form.
Denote by 
the set of all products of 
matrices from
for 
.
DISTRIBUTIONAL MATRIX REPRESENTABILITY PROBLEM
Instance. Matrix , a set of matrices
,
and a positive integer 
. All matrices are
matrices with integer entries. The size of the instance is
.
Question. Is 
?
Distribution. Randomly and independently choose integer
, , and all the entries in the matrices with respect
to the default uniform distributions on integers and binary
strings.
The distributional matrix representability problem was
shown to be average-case NP-complete by Venkatesan and
Rajagopalan [VR92].
It is easy to see that the above distributional problems
are all
in DistNP by noting
that the size of a positive integer is itself (we
may use a unary notation such as 
to denote for this purpose).