<p>As pointed out by Emil, and I think maybe the OP already knew based on the last sentence of the OQ, there isn't actually a uniform distribution on a countable set.</p>
<p>However, Jack Lutz developed the notion of &quot;resource-bounded measure&quot;, whereby one can meaningfully talk about, e.g. the &quot;P-measure of <span class="math-container">$\mathsf{P}$</span> (or <span class="math-container">$\mathsf{NP}$</span>, etc.) inside <span class="math-container">$\mathsf{EXP}$</span>&quot;. This started with <a href="https://doi.org/10.1137/0219076" rel="noreferrer">https://doi.org/10.1137/0219076</a>, and many things were worked on in this area since. For a while (maybe, 10-15 years) John Hitchcock maintained a <a href="https://www.cs.uwyo.edu/%7Ejhitchco/bib/rbm.shtml" rel="noreferrer">bibliography of papers in the area</a>. Elvira Mayordomo is another researcher with a significant amount of work on this area. If you look at papers by any one of these three, together with papers they cite and that cite them, that should get most of the papers on the topic.</p>
<p>Off the top of my head, I don't remember if anyone worked on measure within PSPACE, but the definition of resource-bounded measure is based on a characterization of (ordinary) measure in terms of martingales (which I believe originated with Lutz's paper, even though it is a purely &quot;classical measure theory&quot; result!), and then you get resource-bounded versions by restricting the complexity of the martingales. Presumably if one restricted their complexity to be something like logspace it could give a reasonable notion of resource-bounded measure within PSPACE (there is an exponential blow-up thing happening, just as P-measure gives a good notion inside EXP).</p>

CC BY-SA 4.0
2024-05-02T17:52:49.643Z
It took some time to skim but I think this is exactly what I was asking, thank you for the direction!
abrahimladha
CC BY-SA 4.0
2024-05-02T18:27:09.800Z
PS I think the conjectured answer is that the "resource-bounded measure of P within PSPACE" should be either 0 (a natural strengthening of P \neq PSPACE) *or* P should be an unmeasurable set within PSPACE, sort of fractal-like.
Joshua Grochow
CC BY-SA 4.0
2024-05-12T18:28:12.977Z
(Oh BTW unmeasurable is also a strengthening of P \neq PSPACE, bc it they were equal it'd be measurable of measure 1)
Joshua Grochow
CC BY-SA 4.0
2024-05-02T16:49:43.357Z
2024-05-02T16:49:43.357Z
Joshua Grochow
<p>Suppose I am drawing a venn diagram of complexity classes, and I don't want one that is the most visually pleasing, but the most accurate. How much of PSPACE should P take up?</p>
<p>Let <span class="math-container">$L$</span> be chosen uniformly random from <span class="math-container">$\mathsf{PSPACE}$</span>. What is <span class="math-container">$P[L \in \mathsf{P}]$</span> ? I would like to see if there is a more general answer to this question for any set of complexity classes.</p>
<p>I don't think the notion of measure or countability helps here since (almost) all complexity classes are countably infinite</p>

CC BY-SA 4.0
2024-05-02T16:23:13.313Z
There is no such thing as a "uniformly random" distribution on a countable infinite set.
Emil Jeřábek
CC BY-SA 4.0
2024-05-02T16:51:45.707Z
@EmilJeřábek Reading more, I see the formalization is insufficient, but I think the question could still have an answer. Take either the construction used in Chaitins constant and ask what is the probability a random program has a polynomial time bound conditioned on the fact it has a polynomial space bound. Another way may be to ask about natural density. I suppose I am also asking on a formalization of this question.
abrahimladha
CC BY-SA 4.0
2024-05-02T18:10:43.623Z
Would the problem make sense if instead of considering languages, one would consider randomly selected Turing machines?
Bartosz Bednarczyk
<reference-request><complexity-classes>
What is the probability a random language in $\mathsf{PSPACE}$ is in $\mathsf{P}$?
abrahimladha
# What is the probability a random language in $\mathsf{PSPACE}$ is in $\mathsf{P}$?

(Asked by: username_0 on 2024-05-02)

Suppose I am drawing a venn diagram of complexity classes, and I don't want one that is the most visually pleasing, but the most accurate. How much of PSPACE should P take up?

Let $L$ be chosen uniformly random from $\mathsf{PSPACE}$. What is $P[L \in \mathsf{P}]$ ? I would like to see if there is a more general answer to this question for any set of complexity classes.

I don't think the notion of measure or countability helps here since (almost) all complexity classes are countably infinite

**Tags:** reference-request, complexity-classes
> **Comments:**
> **username_1**: There is no such thing as a "uniformly random" distribution on a countable infinite set.  
> **username_0**: @EmilJeřábek Reading more, I see the formalization is insufficient, but I think the question could still have an answer. Take either the construction used in Chaitins constant and ask what is the probability a random program has a polynomial time bound conditioned on the fact it has a polynomial space bound. Another way may be to ask about natural density. I suppose I am also asking on a formalization of this question.  
> **username_2**: Would the problem make sense if instead of considering languages, one would consider randomly selected Turing machines?  

---

## 1 answers

### Answer by username_3 on 2024-05-02. Score: 6 | Accepted answer

As pointed out by Emil, and I think maybe the OP already knew based on the last sentence of the OQ, there isn't actually a uniform distribution on a countable set.

However, Jack Lutz developed the notion of "resource-bounded measure", whereby one can meaningfully talk about, e.g. the "P-measure of $\mathsf{P}$ (or $\mathsf{NP}$, etc.) inside $\mathsf{EXP}$". This started with <https://doi.org/10.1137/0219076>, and many things were worked on in this area since. For a while (maybe, 10-15 years) John Hitchcock maintained a [bibliography of papers in the area](https://www.cs.uwyo.edu/%7Ejhitchco/bib/rbm.shtml). Elvira Mayordomo is another researcher with a significant amount of work on this area. If you look at papers by any one of these three, together with papers they cite and that cite them, that should get most of the papers on the topic.

Off the top of my head, I don't remember if anyone worked on measure within PSPACE, but the definition of resource-bounded measure is based on a characterization of (ordinary) measure in terms of martingales (which I believe originated with Lutz's paper, even though it is a purely "classical measure theory" result!), and then you get resource-bounded versions by restricting the complexity of the martingales. Presumably if one restricted their complexity to be something like logspace it could give a reasonable notion of resource-bounded measure within PSPACE (there is an exponential blow-up thing happening, just as P-measure gives a good notion inside EXP).

> **Comments:**
> **username_0**: It took some time to skim but I think this is exactly what I was asking, thank you for the direction!  
> **username_3**: PS I think the conjectured answer is that the "resource-bounded measure of P within PSPACE" should be either 0 (a natural strengthening of P \neq PSPACE) *or* P should be an unmeasurable set within PSPACE, sort of fractal-like.  
> **username_3**: (Oh BTW unmeasurable is also a strengthening of P \neq PSPACE, bc it they were equal it'd be measurable of measure 1)  

---

