patternMinor
Probability Distributions and Computational Complexity
Viewed 0 times
computationaldistributionsprobabilityandcomplexity
Problem
This question is about the intersection of probability theory and
computational complexity. One key observation is that some
distributions are easier to generate than others. For example,
the problem
Given a number $n$, return a uniformly distributed number $i$ with $0 \leq i < n$.
is easy to solve. On the other hand, the following problem is or
appears to be much harder.
Given a number $n$, return a number $i$ such that $i$ is (the
Gödel number of) a valid proof of length n in Peano arithmetic.
Moreover, if the number of such proofs is $pr(n)$,
then the probability to get any specific proof of length $n$
should be $\frac{1}{pr(n)}$.
This suggests to me that probability distributions come with a notion
of computational complexity. Moreover, this complexity is probably
closely related to the underlying decision problems (whether sub-recursive,
e.g. $P$, $EXP$, recursive, recursively enumerable, or worse).
My question is: how does one define the computational complexity of probability distributions, especially where the underlying decision problem is not decidable. I'm sure this has been investigated already, but I'm not sure where to look.
computational complexity. One key observation is that some
distributions are easier to generate than others. For example,
the problem
Given a number $n$, return a uniformly distributed number $i$ with $0 \leq i < n$.
is easy to solve. On the other hand, the following problem is or
appears to be much harder.
Given a number $n$, return a number $i$ such that $i$ is (the
Gödel number of) a valid proof of length n in Peano arithmetic.
Moreover, if the number of such proofs is $pr(n)$,
then the probability to get any specific proof of length $n$
should be $\frac{1}{pr(n)}$.
This suggests to me that probability distributions come with a notion
of computational complexity. Moreover, this complexity is probably
closely related to the underlying decision problems (whether sub-recursive,
e.g. $P$, $EXP$, recursive, recursively enumerable, or worse).
My question is: how does one define the computational complexity of probability distributions, especially where the underlying decision problem is not decidable. I'm sure this has been investigated already, but I'm not sure where to look.
Solution
The complexity of probability distributions
comes up particularly in the study of distributional problems like
DistNP in Levin's theory of average case complexity theory.
A distribution is P-computable if
its cumulative density function can be evaluated in polynomial time.
A distribution is P-samplable if
we can sample from them in polynomial time.
If a distribution is P-computable then it is P-sampable.
The reverse is not true if certain one-way functions exist.
You can extend the definitions to other complexity classes.
Oded Goldreich has a nice introductory notes on the topic
that you may want to check.
comes up particularly in the study of distributional problems like
DistNP in Levin's theory of average case complexity theory.
A distribution is P-computable if
its cumulative density function can be evaluated in polynomial time.
A distribution is P-samplable if
we can sample from them in polynomial time.
If a distribution is P-computable then it is P-sampable.
The reverse is not true if certain one-way functions exist.
You can extend the definitions to other complexity classes.
Oded Goldreich has a nice introductory notes on the topic
that you may want to check.
Context
StackExchange Computer Science Q#26485, answer score: 2
Revisions (0)
No revisions yet.