András Salamon
• Member for 11 years, 5 months
• Last seen more than a week ago
• Edinburgh, UK

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

This can be done in nearly linear time. Let the permutation be $\pi = (v_1,\dots,v_m)$, and let $k = k(\pi)$ be the number of steps needed to check a single edge $(u,v)$ against $\pi$. It is then ...

There do seem to be many "good" notions of sparsity, but there is something of a hierarchy for those structural notions of sparsity that have a model-theoretic flavour. I think these have had a ...

See OEIS sequence A054924 for discussion and references. As far as I know this grows faster than any polynomial. In particular, see the sequence of the largest value of |G(n,m)| for each $n$.

You seem to be really asking: is Nurikabe in NP? Nurikabe is NP-hard, since one can build polynomial-size gadgets that can be used to reduce an NP-complete problem to a Nurikabe decision problem. ...

The high-level description of the automated proof by Gonthier is worth reading, if you are looking for more insight. Yuri Matiyasevich studied several probabilistic restatements of the Four Colour ...

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, ...

Most of what you are looking for is well-covered in the survey Stefano Ceri, Georg Gottlob, and Letizia Tanca, What you always wanted to know about Datalog (and never dared to ask), IEEE Transactions ...

This question has two parts: first, is the problem in NP, and second, is it NP-hard? For the first part, I have a positive answer with a non-obvious proof. (Thanks to Suresh for pointing out an ...

Peter Shor observed that by rescaling, this problem becomes about packing unit squares into a convex polygon. Edit: the remainder of this answer does not apply, as it drops the explicitly stated ...

Following the specific reference provided by Steve Huntsman in his MO answer leads to the paper Oded Regev and Ricky Rosen. Lattice problems and norm embeddings, STOC 2006. doi: 10.1145/1132516....

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

Edit: I am leaving this answer as is (for now) to illustrate the messy process of proving theorems, something that is left out of published papers. The core intuition here is that it is enough to ...

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

Consider a complete binary tree with all $2^n$ leaves containing 0, except one leaf that contains 1. The task is to find the leaf that contains 1. Against any deterministic search algorithm it is ...

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

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

I see the padding arguments in terms of compactness of representation. Think of two translator Turing machines: $B$ blows up instances, and $C$ compresses them again. The padding argument works with ...

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

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

As far as I understand, the submodular minimization case captures all there is to be said about the monotone Boolean case, and binary submodular Boolean functions can express all submodular Boolean ...

I'm not altogether convinced by the previous work on open and interactive constraints. An attempt to study the tractability questions was: Martin J. Green and Christopher Jefferson, Structural ...

As stated (revision 3), the question has a simple answer: no. The reason is that even for the highly restricted class of representations given by Boolean circuits with AND, OR, and NOT gates, no ...

Some observations, not an answer. Further to the note to the question, any combination of 3 literals can be expressed in terms of any other combination of literals on the same variables, together ...

Some comments: not an answer. If $c$ is small enough with respect to the number of vertices in the graph, then the improper colourings will add up to less than 1. Hence there is a trivial reduction ...

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

You linked to two papers, both with conjectures. I presume you mean Grohe's 2007 conjecture. This question was answered in 2008: Theorem 5. CSP(C$_0$,_) is in NP, but neither in P nor NP-complete ...

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