Timeline for What is the probability a random language in $\mathsf{PSPACE}$ is in $\mathsf{P}$?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2 at 18:10 | comment | added | Bartosz Bednarczyk | Would the problem make sense if instead of considering languages, one would consider randomly selected Turing machines? | |
| May 2 at 17:49 | vote | accept | abrahimladha | ||
| May 2 at 16:51 | comment | added | 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. | |
| May 2 at 16:49 | answer | added | Joshua Grochow | timeline score: 6 | |
| May 2 at 16:23 | comment | added | Emil Jeřábek | There is no such thing as a "uniformly random" distribution on a countable infinite set. | |
| May 2 at 15:42 | history | asked | abrahimladha | CC BY-SA 4.0 |