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

52 votes
11 answers
16k views

Recent advances in computer science since 2010?

2 votes
0 answers
30 views

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

3 votes
1 answer
314 views

Dynamic transitive closure with immediate new reachability facts

3 votes
1 answer
55 views

Assignment problem for forming pairs of real numbers

1 vote
0 answers
47 views

Equivalence between GNFA and NFA/DFA

3 votes
0 answers
80 views

Fast algorithms for time bounded Kolmogorov complexity

10 votes
1 answer
788 views

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

0 votes
1 answer
69 views

Exchange cards with sum requirement

5 votes
2 answers
217 views

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

1 vote
0 answers
39 views

Elimination of monadic second-order quantifiers

0 votes
0 answers
39 views

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

5 votes
0 answers
119 views

Could a quantum computer prove theorems with infeasibly long proofs?

41 votes
5 answers
6k views

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

1 vote
0 answers
62 views

Tractability of computing generalized hypertreewidth on bounded arity hypergraphs

Browse more Questions