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

Explore our questions

1 vote
0 answers
83 views

Is the protocol perfect zero knowledge?

7 votes
2 answers
331 views

Problems where "maximal" is hard, but "maximum" is easy?

5 votes
1 answer
165 views

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

4 votes
0 answers
92 views

Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?

1 vote
0 answers
174 views

Perm and Det mod $2^k$ - II

3 votes
0 answers
62 views

Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

0 votes
0 answers
55 views

Why can't we just reduce from Bounded HALT to Bounded PCP?

4 votes
0 answers
150 views

Is there a 'mathematical program' to separate P from BQP?

1 vote
0 answers
75 views

Are there any candidate languages in NE but not E?

-1 votes
1 answer
135 views

Solve 3CNF in Poly-Time with Satisfiability Oracle

4 votes
1 answer
156 views

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

5 votes
0 answers
264 views

What's wrong with this $P \neq BPP$ proof?

8 votes
1 answer
485 views

What can we do with a generic oracle (as opposed to a random one)?

1 vote
0 answers
76 views

Crafting ${NP}^{\#P}$-complete problems

Browse more Questions