András Salamon
  • Member for 11 years, 5 months
  • Last seen more than a week ago
Major unsolved problems in theoretical computer science?
147 votes

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

View answer
Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming
51 votes

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

View answer
Major unsolved problems in theoretical computer science?
41 votes

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

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
Circuit lower bounds over arbitrary sets of gates
Accepted answer
25 votes

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

View answer
Complexity zoo for unary languages
Accepted answer
23 votes

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

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 good references to understanding the proof of the PCP theorem?
23 votes

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

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
What does one mean by heuristic statistical physics arguments?
Accepted answer
22 votes

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

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
Why is 2SAT in P?
20 votes

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

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
Overarching reasons why problems are in P or BPP
19 votes

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

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
A simple decision problem whose decidability is not known
18 votes

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

View answer
Problems Between P and NPC
18 votes

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

View answer
Dinner-table description of theoretical computer science?
18 votes

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

View answer
Current tightest bounds for critical 3-SAT density
17 votes

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

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
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
Is Almost-2-SAT NP-hard?
15 votes

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

View answer
Ladner's Theorem vs. Schaefer's Theorem
Accepted answer
15 votes

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

View answer
Complexity of "is a graph a product"
15 votes

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

View answer
Barriers and Monotone Circuit Complexity
Accepted answer
15 votes

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

View answer
How do database aggregations form a monoid?
Accepted answer
14 votes

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

View answer
Overarching reasons why problems are in P or BPP
14 votes

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

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
Nontrivial membership in NP
13 votes

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

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