Can multiplication of $n$ by $n$ matrices be done in $O(n^2)$ operations? The exponent of the best known upper bound even has a special symbol, $\omega$. Currently $\omega$ is approximately 2.376, by ...

SAT, CP, SMT, (much of) ASP all deal with the same set of combinatorial optimisation problems. However, they come at these problems from different angles and with different toolboxes. These ...

Are there problems that cannot be solved efficiently by parallel computers? Problems that are P-complete are not known to be parallelizable. P-complete problems include Horn-SAT and Linear ...

If your SAT algorithm is meant to be practical, then you should run the SAT competition benchmarks on it. The SAT solving community is going to take your work much more seriously if you can show that ...

(Moved from comments as Suresh suggested. Note some errors in the comment are fixed here.) Thanks to Scott for a great question. Scott seems to suggest that the reason for the difficulty of lower ...

There is no Zoo-style reference yet, but a recent automata-theoretic survey of Giovanni Pighizzini has been useful to me, especially the slides from his talk. Giovanni Pighizzini, Investigations on ...

The most general result known is by Grohe. A summary was presented in July 2010: Martin Grohe, Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors, LICS 2010. (PDF) In ...

Dinur's paper (linked in the answer by Daniel Apon) is well written and worth reading. An extended discussion was also published about this paper and the proof, which is useful when reading the paper ...

Computing the core of a graph is hard: even deciding if a given 3-colourable graph is a core is co-NP-complete, see Hell and Nesetril. There are settings where core computation can be done ...

The second paragraph of RJK's response deserves more detail. Let $\phi$ be a formula in conjunctive normal form, with m clauses, n variables, and at most k variables per clause. Suppose we want to ...

INDEPENDENT SET is NP-complete for (cross,triangle)-free graphs, but can be solved in linear time for (chair,triangle)-free graphs. (The X-free graphs are those that contain no graph from X as an ...

As Walter says, clauses of 2-SAT have a special form. This can be exploited to find solutions quickly. There are actually several classes of SAT instances that can be decided in polynomial time, and ...

Dimitris Achlioptas covers this in a survey article from the first edition of the Handbook of Satisfiability (PDF of draft). There is conjectured to be a single threshold $r_k$ for each $k \ge 3$, so ...

Some graph classes allow polynomial-time algorithms for problems that are NP-hard for the class of all graphs. For instance, for perfect graphs, one can find a largest independent set in polynomial ...

I am not sure I would go along with your characterization that adding a single edge to the input makes the problem NP-complete, since one is actually allowing an edge to be added to every one of the ...

The decidability of conjunctive query containment has been open for over twenty years. Resolving this would be a breakthrough in database theory. Query containment takes as input two queries $Q_1$ ...

In a monotone CNF formula every clause contains only positive literals or only negative literals. In an intersecting monotone CNF formula every positive clause has some variable in common with every ...

An example answer, which can definitely be improved: Theoretical computer scientists study computation in mathematical terms. They can fix your computer about as well as mathematicians can ...

Notwithstanding Friedgut's theorem about $k$-SAT, while we lack techniques to get to negligible $\epsilon$ for small $k$, it seems more useful to talk about the satisfiability threshold ($\alpha - \...

It is not even known whether NC = P, but P-complete problems seem to be inherently hard to parallelize. These include Linear Programming and Horn-SAT. (In contrast, problems in NC seem reasonably ...

There are large classes of queries which are "easy", even in the worst case. In particular, if the class of queries contains conjunctive queries only and each query has bounded width (for instance ...

It is worth noting that the problem becomes NP-hard when the restriction is relaxed slightly. With a fixed number of clauses that are also of bounded size, the average number of literals in a clause ...

As Massimo Lauria states, problems of the form CSP($\Gamma$) are rather special. So there is no contradiction. Any constraint satisfaction problem instance can be represented as a pair $(S,T)$ of ...

Several graph products can be recognized in polynomial time. As usual the Cartesian product is the easiest, and the Cartesian case is also the basis for the algorithms for several other products. ...

Benjamin Rossman's recent paper summarises the state of the art for the monotone circuit complexity of k-CLIQUE. In short, Razborov proved a lower bound in 1985, later improved by Alon and Boppana in ...

You ask why database aggregations have monoidal structure. Say we want to combine data values $a$ and $b$, but want to keep things general -- these may be integers, strings, floating point numbers, ...

There is a large and still growing body of theory about classes of fixed-template constraint satisfaction problems that have polynomial-time algorithms. Much of this work requires mastery of the Hobby ...

The complement of a vertex cover is an independent set. Your question is therefore equivalent to asking whether counting independent sets is #P-complete on trees. The answer to this question is NO, ...

My favourite example is a classic 1977 result of Ashok Chandra and Philip Merlin. They showed that the query containment problem was decidable for conjunctive queries. The conjunctive query ...

It sounds like you are looking for a characterisation of the features required to capture diagonalization arguments. Lawvere's Diagonal Arguments and Cartesian Closed Categories unified each of the ...