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
52 votes
11 answers
16k views

Recent advances in computer science since 2010?

usul's user avatar
usul
  • 7,535
2 votes
0 answers
30 views

FPRAS to estimate the probability to get a cyclic subgraph of a directed graph

a3nm's user avatar
a3nm
  • 8,836
3 votes
1 answer
314 views

Dynamic transitive closure with immediate new reachability facts

Community's user avatar
CommunityBot
  • 1
3 votes
1 answer
55 views

Assignment problem for forming pairs of real numbers

D.W.'s user avatar
D.W.
  • 11.6k
1 vote
0 answers
47 views

Equivalence between GNFA and NFA/DFA

Abced Decba's user avatar
Abced Decba
  • 111
3 votes
0 answers
80 views

Fast algorithms for time bounded Kolmogorov complexity

agemO's user avatar
agemO
  • 131
10 votes
1 answer
788 views

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

Peter Mortensen's user avatar
Peter Mortensen
  • 113
0 votes
1 answer
69 views

Exchange cards with sum requirement

Community's user avatar
CommunityBot
  • 1
5 votes
2 answers
217 views

What are the consequences of $BPP \neq P$?

Andras Farago's user avatar
Andras Farago
  • 11.3k
1 vote
0 answers
39 views

Elimination of monadic second-order quantifiers

gigabytes's user avatar
gigabytes
  • 1,558
0 votes
0 answers
39 views

Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?

hedgehog0's user avatar
hedgehog0
  • 1
5 votes
0 answers
119 views

Could a quantum computer prove theorems with infeasibly long proofs?

Timothy Chow's user avatar
Timothy Chow
  • 7,417
41 votes
5 answers
6k views

What is the smallest Turing machine where it is unknown if it halts or not?

Ciro Santilli OurBigBook.com's user avatar
Ciro Santilli OurBigBook.com
  • 211
1 vote
0 answers
62 views

Tractability of computing generalized hypertreewidth on bounded arity hypergraphs

a3nm's user avatar
a3nm
  • 8,836
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.