Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

The number of clauses in an unsatisfiable CNF

I am interested in generalisations of the following observation: An unsatisfiable $k$-CNF has at least $2^k$ clauses. A special case of the observation is when $k=n$, where $n$ is the number of ...

reference-request graph-theory sat  
asked by Christopher Purcell 10 votes
answered by Christian Komusiewicz 4 votes

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

Let $CC^0[m]$ be the class of constant-depth, polynomial-sized circuits consisting entirely of $MOD_m$ gates, which put out $1$ iff the sum of their inputs $\equiv 0~(\textrm{mod}~m)$. In the same way ...

lo.logic circuit-complexity uniformity  
asked by cheeze 2 votes

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

I'm looking for an explanation of critical pairs and the Knuth-Bendix completion algorithm that is at once rigorous and of high pedagogical value, i.e. clear, detailed, containing illustrative ...

reference-request term-rewriting-systems first-order-logic  
asked by Evan Aad 1 vote

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

Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J_1, J_2, \dots, J_n$ to be lists of vertices where list $J_i$ consists of vertex $v_i \in V$ and all ancestors of $v_i$....

ds.algorithms graph-theory graph-algorithms ds.data-structures directed-acyclic-graph  
asked by user1246462 1 vote
answered by daniello 2 votes

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

I’ve been reading up on the connection between first order logic and small circuit complexity classes, and specifically Barrington, Immerman, and Straubing’s paper “On Uniformity Within $\mathit{NC}^1$...

lo.logic uniformity ac0  
asked by cheeze 1 vote

How does complexity of a counting problem influence wether it admits a closed form formula or not?

In https://arxiv.org/abs/1412.1505, the section "Results on Data Complexity" mentions the fact that since the authors are about to proove $\#P_1$ complexity for weighted model counting in ...

counting-complexity first-order-logic  
asked by SagarM 1 vote

Greatest hits from previous weeks:

Applicability of Church-Turing thesis to interactive models of computation

Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere. ...

computability turing-machines machine-models church-turing-thesis  
asked by zenna 39 votes
answered by Scott Aaronson 75 votes

How practical is Automata Theory?

There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important ...

soft-question fl.formal-languages automata-theory teaching  
asked by Dark Templar 38 votes
answered by Anonymous 52 votes

Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct? Also on topic: where else (on the internet) is its correctness being discussed? Note: the focus of this question text has ...

cc.complexity-theory np-hardness complexity-classes  
asked by Warren Schudy 232 votes
answered by idolvon 97 votes

Universities for Quantum Computing / Information?

Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research? The aim here is to collect a useful list for someone considering ...

soft-question quantum-computing big-list quantum-information  
asked by Vincent Russo 20 votes
answered by Joe Fitzsimons 20 votes

what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?

Both problems are well-known NP-hard problems with great similarities. In fact, I do not see the real difference between these two problems. It seems relatively easy to model TSR in the form of VRP ...

cc.complexity-theory np-hardness tsp  
asked by sma 5 votes
answered by Marzio De Biasi 4 votes

What is the best text of computation theory/theory of computation?

In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression. I borrowed that book and ...

reference-request soft-question computability books  
asked by Recursion 9 votes

tournament selection in genetic algorithms

I have a question about how to use a tournament selection in GA. Suppose that I have 100 individuals as an initial population and then I want to apply tournament selection for n generations, so I end ...

genetic-algorithms selection  
asked by Manolo 4 votes
answered by deong 12 votes
You're receiving this message because you subscribed to the Theoretical Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy
Stack Overflow

Stack Overflow, 110 William Street, 28th floor, New York, NY 10038

<3