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
Theoretical Computer Science

Explore our questions

Ask Question
more tags
Active Hot Week Month
-2 votes
1 answer
87 views

Proof that DFS order is P-complete

Robin Petr's user avatar
Robin Petr
  • 1
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?

rus9384's user avatar
rus9384
  • 275
8 votes
1 answer
404 views

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

Emil Jeřábek's user avatar
Emil Jeřábek
  • 16.9k
1 vote
0 answers
64 views

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

Habri's user avatar
Habri
  • 11
0 votes
0 answers
99 views

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

Zazaeil's user avatar
Zazaeil
  • 212
2 votes
1 answer
277 views

Deciding finiteness of regular language is NL-complete?

Bartosz Bednarczyk's user avatar
Bartosz Bednarczyk
  • 1,330
5 votes
1 answer
388 views

Relation between ACC^0 and DTIME

Ryan Williams's user avatar
Ryan Williams
  • 27.3k
0 votes
0 answers
166 views

Decidability of the complexity of decision problems

A. G's user avatar
A. G
  • 101
3 votes
0 answers
111 views

Computational complexity of finding the $n$th Dedekind Number

Clay Thomas's user avatar
Clay Thomas
  • 205
1 vote
1 answer
109 views

Complexity of analytic functions and integrals

Emil Jeřábek's user avatar
Emil Jeřábek
  • 16.9k
5 votes
0 answers
125 views

Do fast satisfiability algorithms imply fast algorithms for parity SAT?

Michael Lampis's user avatar
Michael Lampis
  • 3,416
12 votes
2 answers
426 views

Ruzzo-Simon-Tompa oracle access mechanism

Eric Allender's user avatar
Eric Allender
  • 1,761
10 votes
1 answer
805 views

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

Peter Mortensen's user avatar
Peter Mortensen
  • 113
1 vote
0 answers
77 views

What complexity class is characterized by having PSPACE verifiers?

Ilk's user avatar
Ilk
  • 900
Browse more Questions

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.