Top new questions this week:
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
|
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$....
|
|
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$...
|
|
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 ...
|
Greatest hits from previous weeks:
|
|
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. ...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
