Suppose we define a class of algorithms that is allowed to sample i.i.d. Bernoulli bitstrings of arbitrary length, and use these to generate outputs. If we are allowed to use algorithms like this, then intuitively, "white noise" images like this one are easy to generate (i.e they have a low description length algorithm allowing random noise, even though it is essentially maximum k-complexity), namely we just run a for loop width x height times and pick black/white randomly.

I've tried to look online for "stochastic algorithmic complexity" and some other keywords, but haven't found anything relevant. Is there a term that I can search for to read about this idea, of defining an algorithmic complexity measure of objects/classes of objects using algorithms that are allowed to use randomness?


1 Answer 1


One possible direction is looking at the (computational) hardness of distributions. For example, a family of distributions $\{\mathcal{P}_n\}_{n\in\mathbb{N}}$ where $\mathcal{P}_n$ is a distribution over $\{0,1\}^n$ is called polynomialy-samplable (you can substitute here any other type of time/space restriction) if there exists a probabilistic polynomial time algorithm $A$ such that $A(1^n)\sim \mathcal{P}_n$. Your white noise example translates in this case to the uniform distribution being easy (samplable). These notion often arise in average case complexity, where one cares about the average hardness of computing a function relative to some backgroud distribution over the inputs. A straightforward generalization of this would be to restrict the distance (total variation/KL) between $A(1^n)$ and $\mathcal{P}_n$.

In any case, whenever one is interested in computational hardness, you would probably have to introduce a family of objects rather than talk about the complexity of a specific member.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.