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
4 votes
1 answer
138 views

Fast algorithms for time bounded Kolmogorov complexity

agemO's user avatar
agemO
  • 143
0 votes
0 answers
36 views

Do pseudo-random number generator test batteries have any theoretical grounding?

uhbif19's user avatar
uhbif19
  • 271
36 votes
7 answers
8k views

What's the simplest noncontroversial 2-state universal Turing machine?

ais523's user avatar
ais523
  • 121
1 vote
1 answer
75 views

Approximating the utilitarian welfare minus a constant

Community's user avatar
CommunityBot
  • 1
0 votes
1 answer
196 views

Is it known that P $\neq$ NP implies BQP $\neq$ NP?

108_mk's user avatar
108_mk
  • 1
5 votes
0 answers
65 views

Certifying the promise in hard promise problems

Noel Arteche's user avatar
Noel Arteche
  • 729
-1 votes
0 answers
46 views

Introduction to complexity calculation

MOHAMED SALHI's user avatar
MOHAMED SALHI
  • 1
2 votes
0 answers
41 views

Why is showing lower bounds for AM communication complexity difficult?

Naysh's user avatar
Naysh
  • 526
3 votes
1 answer
118 views

is SUBEXP contained within PSPACE?, NP?

Eric Allender's user avatar
Eric Allender
  • 1,156
55 votes
11 answers
16k views

Recent advances in computer science since 2010?

usul's user avatar
usul
  • 7,565
3 votes
0 answers
52 views

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

a3nm's user avatar
a3nm
  • 8,866
3 votes
1 answer
317 views

Dynamic transitive closure with immediate new reachability facts

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

Assignment problem for forming pairs of real numbers

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

Equivalence between GNFA and NFA/DFA

Abced Decba's user avatar
Abced Decba
  • 111
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.