András Salamon
  • Member for 11 years, 5 months
  • Last seen more than a week ago
Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?
16 votes

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

View answer
Testing/Identifying a Topological Sorting
3 votes

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

View answer
What is the most important notion of sparsity for the design of efficient graph algorithms?
8 votes

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

View answer
Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges
5 votes

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

View answer
What is the complexity of (possibly succinct) Nurikabe?
6 votes

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

View answer
Conjectures implying Four Color Theorem
9 votes

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

View answer
Trees: complexity of counting the number of vertex covers
Accepted answer
14 votes

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

View answer
DATALOG references
Accepted answer
10 votes

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

View answer
Is the half-filled magic square problem NP-complete?
9 votes

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

View answer
Packing rectangles into convex polygons but without rotations
1 votes

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

View answer
Other norms for Lattice reduction techniques (LLL, PSLQ)?
Accepted answer
4 votes

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

View answer
Is one definition of the word paradox, "something that can be used to prove the halting problem undecidable?"
Accepted answer
13 votes

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

View answer
Avalanche like stochastic process
9 votes

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

View answer
What is the best exact algorithm to compute the core of a graph?
22 votes

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

View answer
Randomized algorithm that "looks" deterministic?
12 votes

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

View answer
Hardness jumps in computational complexity?
21 votes

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

View answer
Hardness jumps in computational complexity?
19 votes

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

View answer
Why do equalities between complexity classes translate upwards and not downwards?
13 votes

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

View answer
what is easy for minor-excluded graphs?
Accepted answer
23 votes

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

View answer
What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?
Accepted answer
19 votes

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

View answer
Reference Request: Submodular Minimization and Monotone Boolean Functions
Accepted answer
7 votes

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

View answer
Open or Interactive Constraint Satisfaction
9 votes

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

View answer
Compactly representing the solution set of a SAT instance
10 votes

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

View answer
Counting solutions of Monotone-2CNF formulas
7 votes

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

View answer
When is relaxed counting hard?
4 votes

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

View answer
Limits to Parallel Computing
17 votes

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

View answer
CSPs with unbounded fractional hypertree width
Accepted answer
8 votes

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

View answer
Where do I turn for help with research/publishing?
Accepted answer
32 votes

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

View answer
Finding the penumbra of a Constraint Satisfaction Problem
6 votes

Much of the attention paid to optimization variants of the constraint satisfaction problem (CSP) has focused on satisfying some number of constraints (MAX-CSP), or in the Boolean case on picking the ...

View answer
Using SAT for Computer Vision tasks
Accepted answer
6 votes

Many problems in computer vision are naturally expressed as constraint satisfaction problems. There is a history going back several decades of applying constraint programming to such problems. One ...

View answer