  Consider a d*n matrix A, with d<n. The problem of solving for x in y=Ax is
underdetermined, and has infinitely many solutions (if there are any). Given y,
the minimum Kolmogorov complexity solution (MKCS) of the input x is defined to
be an input z (out of many) with minimum Kolmogorov-complexity that satisfies
y=Az. One expects that if the actual input is simple enough, then MKCS will
recover the input exactly. This paper presents a preliminary study of the
existence and value of the complexity level up to which such a complexity-based
recovery is possible. It is shown that for the set of all d*n binary matrices
(with entries 0 or 1 and d<n), MKCS exactly recovers the input for an
overwhelming fraction of the matrices provided the Kolmogorov complexity of the
input is O(d). A weak converse that is loose by a log n factor is also
established for this case. Finally, we investigate the difficulty of finding a
matrix that has the property of recovering inputs with complexity of O(d) using
MKCS.
