What is the probability a random language in $\mathsf{PSPACE}$ is in $\mathsf{P}$?

Question

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

• Emil Jeřábek: There is no such thing as a "uniformly random" distribution on a countable infinite set.
• abrahimladha: @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.
• Bartosz Bednarczyk: Would the problem make sense if instead of considering languages, one would consider randomly selected Turing machines?

Answer 1

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. 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).

• abrahimladha: It took some time to skim but I think this is exactly what I was asking, thank you for the direction!
• Joshua Grochow: 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: (Oh BTW unmeasurable is also a strengthening of P \neq PSPACE, bc it they were equal it'd be measurable of measure 1)