5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ There is no such thing as a "uniformly random" distribution on a countable infinite set. $\endgroup$
    – Emil Jeřábek
    Commented May 2 at 16:23
  • $\begingroup$ @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. $\endgroup$
    – abrahimladha
    Commented May 2 at 16:51
  • $\begingroup$ Would the problem make sense if instead of considering languages, one would consider randomly selected Turing machines? $\endgroup$
    – Bartosz Bednarczyk
    Commented May 2 at 18:10

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ It took some time to skim but I think this is exactly what I was asking, thank you for the direction! $\endgroup$
    – abrahimladha
    Commented May 2 at 17:52
  • 2
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Commented May 2 at 18:27
  • 1
    $\begingroup$ (Oh BTW unmeasurable is also a strengthening of P \neq PSPACE, bc it they were equal it'd be measurable of measure 1) $\endgroup$
    – Joshua Grochow
    Commented May 12 at 18:28

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.