Skip to main content
Share Your Experience: Take the 2024 Developer Survey
6 votes

What is the probability a random language in $\mathsf{PSPACE}$ is in $\mathsf{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. However, Jack Lutz developed the ...
Joshua Grochow's user avatar
4 votes

The empty tree-word for regular tree languages

I believe this is one of the many cases where it becomes clear that labelling nodes is a bad choice, and we should be labelling edges instead. In the edge-labelled framework, the empty tree is simply ...
Denis's user avatar
  • 8,893
1 vote

Constructing vector valued boolean circuits from boolean circuits

I doubt it. At least, not in all cases. Suppose that you are working in a circuit model where every function $\mathbb{B}^k\to\mathbb{B}$ can be represented by a circuit with $\le 2^k+1$ gates, say by ...
D.W.'s user avatar
  • 12.1k

Only top scored, non community-wiki answers of a minimum length are eligible