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

Ask Question

more tags

Active Hot Week Month

-1

votes

0

answers

6

views

Power of Multi Tape and Multi Track Turing Machine

computability turing-machines universal-computation

asked 1 hour ago Sourabh Yadav 1

1

vote

2

answers

75

views

A clear and rigorous explanation of critical pairs and the Knuth-Bendix completion algorithm?

reference-request term-rewriting-systems first-order-logic

answered 1 hour ago cody 12.4k

-1

votes

0

answers

18

views

Counting valuations in Prolog

sat logic-programming

asked 18 hours ago Gottlob Frege 1

4

votes

0

answers

48

views

Proof of $DLOGTIME-CC^0 = MOD[<,bit]$

lo.logic circuit-complexity uniformity

asked yesterday cheeze 59

0

votes

0

answers

67

views

3-partition problem without the restriction to triplets

reductions partition-problem

modified 2 days ago Erel Segal-Halevi 1,548

0

votes

0

answers

65

views

Approximate counting with non-uniform sampler

counting-complexity

asked 2 days ago Nocturne 101

0

votes

0

answers

48

views

Computational cost of Optimal Morse-Like codes?

information theory prefix free codes

modified Oct 27 at 16:36 Jeremy 2,341

10

votes

1

answer

175

views

The number of clauses in an unsatisfiable CNF

reference-request graph-theory sat

answered Oct 26 at 12:36 Christian Komusiewicz 1,550

1

vote

1

answer

46

views

Separating DAGs using separators consisting of lists of nodes and all ancestors

ds.algorithms graph-theory graph-algorithms ds.data-structures directed-acyclic-graph

answered Oct 26 at 6:49 daniello 2,991

0

votes

0

answers

29

views

Expected value in case of Langevin dynamics

pr.probability upper-bounds approximation stochastic-process

asked Oct 25 at 17:05 Dushyant Sahoo 101

-1

votes

0

answers

57

views

Curry Howard Isomorphism and cut elimination

curry-howard

asked Oct 25 at 16:16 David Lehnherr 99

0

votes

0

answers

14

views

Notation for scheduling problems with multiple release times/deadline intervals

reference-request scheduling notation

asked Oct 25 at 9:55 a3nm 6,786

27

votes

5

answers

4k

views

Counting words accepted by a regular grammar

ds.algorithms co.combinatorics fl.formal-languages regular-language

answered Oct 24 at 15:19 joro 1,905

1

vote

0

answers

87

views

$\mathit{FO}[+,\times]$ seems more powerful than $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$?

lo.logic uniformity ac0

modified Oct 23 at 7:54 Emil Jeřábek 12.1k

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled