 ## 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, 110 William Street, 28th floor, New York, NY 10038

 <3