Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Explore our questions

-2 votes
1 answer
87 views

Proof that DFS order is P-complete

3 votes
0 answers
58 views

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

8 votes
1 answer
404 views

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

1 vote
0 answers
64 views

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

0 votes
0 answers
99 views

Assume `P != NP`, does it imply that one-way functions exist?

2 votes
1 answer
277 views

Deciding finiteness of regular language is NL-complete?

5 votes
1 answer
388 views

Relation between ACC^0 and DTIME

0 votes
0 answers
166 views

Decidability of the complexity of decision problems

3 votes
0 answers
111 views

Computational complexity of finding the $n$th Dedekind Number

1 vote
1 answer
109 views

Complexity of analytic functions and integrals

5 votes
0 answers
125 views

Do fast satisfiability algorithms imply fast algorithms for parity SAT?

12 votes
2 answers
426 views

Ruzzo-Simon-Tompa oracle access mechanism

10 votes
1 answer
805 views

Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

1 vote
0 answers
77 views

What complexity class is characterized by having PSPACE verifiers?

Browse more Questions