Can testing show the absence of bugs?
(This was meant as a comment, but went long).
Very interesting question.
If you are willing to think about other complexity measures besides Kolmogorov's, then there are some answers in Learning theory that might satisfy you. I leave it for the experts in the area.

For example, if I'm not mistaken, in "A theory of the learnable" Valiant proved that a boolean function can be reconstructed given a polynomial number of "positive points" on the size of its k-CNF formula (for any fixed k, and I mean
with "positive points" those of the form $(x_1,\ldots,x_n,1)$).

In Knuth's TAOCP 7.2.1.6 it is shown in an astonishing way (using the Christmas tree pattern) that to reconstruct a monote boolean function (i.e. non-decreasing in each variable) you need exactly ${n+1 \choose \lfloor n/2\rfloor+1}$ points.