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 2 Bountied Hot Week Month
0 votes
0 answers
5 views

How is runtime downcasting modeled in type theory?

nullUser's user avatar
nullUser
  • 101
1 vote
0 answers
21 views
+50

Given several $a_i$-$r$ paths in a planar graph how ``balanced" of a tree rooted at $r$ can I make?

Hao S's user avatar
Hao S
  • 187
1 vote
0 answers
33 views

What is the relation between these two complexity classes -$FL_{log}(ZPLP)$ and $FL_{||}(ZPLP)$?

Turbo's user avatar
Turbo
  • 12.6k
-1 votes
1 answer
93 views

What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?

Mark S's user avatar
Mark S
  • 957
3 votes
1 answer
280 views

Dynamic transitive closure with immediate new reachability facts

Community's user avatar
CommunityBot
  • 1
14 votes
2 answers
1k views

Gaussian Elimination in terms of Group Action

The Amplitwist's user avatar
The Amplitwist
  • 159
3 votes
1 answer
359 views

Can Lexicographic BFS be implemented in logspace?

Siddharth's user avatar
Siddharth
  • 693
3 votes
1 answer
122 views

Is there an efficient algorithm to check for duplicator-invariant equivalence on symmetric interaction combinators?

Damiano Mazza's user avatar
Damiano Mazza
  • 5,233
1 vote
0 answers
15 views

Is minimum knot crossing number elementary recursive?

Niklas Rosencrantz's user avatar
Niklas Rosencrantz
  • 221
0 votes
0 answers
44 views

How to formulate the log-rank conjecture for non-boolean functions?

Alexey Milovanov's user avatar
Alexey Milovanov
  • 1,881
21 votes
2 answers
2k views
+100

What are the #P-complete subfamilies of #2-SAT?

Tuomas Laakkonen's user avatar
Tuomas Laakkonen
  • 191
0 votes
0 answers
14 views

What is an efficient algorithm to check for equivalence on symmetric interaction combinators?

MaiaVictor's user avatar
MaiaVictor
  • 3,077
0 votes
0 answers
39 views

help me understand what semiprime factorizations are worth

claudio G's user avatar
claudio G
  • 1
0 votes
1 answer
56 views

Exchange cards with sum requirement

Community's user avatar
CommunityBot
  • 1
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.