## 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

### 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

### 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

### 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

### $\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

### 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

## 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

### 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

### 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

### 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

### 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

### 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

### 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