1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.