András Salamon
  • Member for 11 years, 5 months
  • Last seen more than a week ago
Does Rabin/Yao exist (at least in a form that can be cited)?
Accepted answer
7 votes

After more than two years, I have to assume the answer is "no". (Posting this stub answer so the question can be marked as answered.)

View answer
Reduction from independent set in hypergraphs to independent set in graphs
1 votes

I am not as convinced as @Andrew Morgan is that this is "fair standard fare", and would also welcome pointers to a citable reduction. In particular, I do not see how to maintain a linear blowup if $k$ ...

View answer
How many tautologies are there?
6 votes

This is an extended comment to complement Ryan's answer, which deals with the thresholds where the number of clauses becomes large enough that the instance is almost surely unsatisfiable. One can also ...

View answer
Packing $n$ objects into $m$ bins whose size is variable
Accepted answer
2 votes

One simple "bad" input that needs to be considered for worst-case analysis of this problem is as follows. Let $c=(\sqrt{17}-1)/2 \approx 1.56$. There are three objects of size $c$, $1$, and $1$. ...

View answer
Fully linear time regular expression matching
Accepted answer
6 votes

Groz et al. explicitly state that the best known algorithm for general regular expressions (as of 2012) is $O(nm(\log\log n)/(\log n)^{3/2}+n+m)$, due to Bille and Thorup 2009, doi:10.1007/978-3-642-...

View answer
Problems Between P and NPC
4 votes

A problem that is not known to be either in FP or to be NP-hard is the problem of finding a minimal Steiner tree when the Steiner vertices are promised to fall on two straight line segments ...

View answer
Can a hereditary graph class contain almost all, but not all, n-vertex graphs?
10 votes

To add to Daniel's answer, the precise density of hereditary classes has been extensively investigated in combinatorics. For a class $C$ of structures, the unlabelled slice $C_n$ is the set of ...

View answer
Evidence that UniqueSat is dense
Accepted answer
4 votes

As far as I can tell, UniqueSAT is exponentially dense, in the sense that it contains $2^{\Omega(n)}$ instances of size $n$. (This is a stronger requirement than $2^{n^\varepsilon}$ for infinitely ...

View answer
Lipton's most influential results
7 votes

Multiparty communication complexity and the Number-on-Forehead model were introduced by Ashok K. Chandra, Merrick L. Furst and Richard J. Lipton in Multi-party Protocols, STOC 1983, doi:10.1145/800061....

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
Research problems in communication complexity
6 votes

Several long-standing key open problems are in the Kushilevitz and Nisan textbook (see also the list of errata which mentions that Open Problem 8.6 was solved by Dietzfelbinger). Razborov's 2011 ...

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
Low space computation and branching program
2 votes

Denoting the class of functions computed by branching programs of size $f(n)$ by $\text{BP}(f)$, the best known bound seems to be the trivial $\text{DSPACE}(S(n)) \subseteq \text{BP}(2^{O(S(n))})$. ...

View answer
Best current space lower bound for SAT?
Accepted answer
3 votes

Looks like the best bound known (for multitape Turing machines) is logarithmic. Suppose $\delta\log n$ bits of binary worktape is enough to decide whether any $n$-bit CNF formula is satisfiable, for ...

View answer
The unreasonable power of non-uniformity
10 votes

For me, the starkest illustration of the power of non-uniformity is that a suitably padded version of the Halting Problem is already in P/1. A single bit of advice is then enough to decide this ...

View answer
Planted Clique in G(n,p), varying p
Accepted answer
9 votes

If $p$ is constant, then the size of the maximum clique in the $G(n,p)$ model is almost everywhere a constant multiple of $\log n$, with the constant proportional to $\log (1/p)$. (See Bollobás, p....

View answer
Learnability of constraint satisfaction problems CSPs?
6 votes

You are probably looking for this paper: Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, TCS 306 485–511, 2003. doi:10.1016/S0304-3975(03)00342-6 In short, the learning ...

View answer
Deterministic communication complexity vs partition number
7 votes

You remark that lower bounds on $Pn(f)$ are closely related to all existing lower bound techniques. For Boolean functions this seems to be true, as long as the log-rank conjecture is true. However, $...

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

Conjunctive query containment over bag semantics In a GoogleFight between two search queries, can one tell if the first query always wins, without looking at the data? This 1993 question from ...

View answer
Using Kolmogorov complexity as input "size"
4 votes

An easy case seems to be where the language $S$ contains only padded instances. When $S$ is obtained from a language $L$ by padding each instance of size $n$ with $2^n-n$ symbols, $f^K_{n}$ can be in ...

View answer
Nontrivial membership in NP
4 votes

Deciding reachability for various kinds of infinite-state systems is sometimes decidable, often not. For some interesting special cases a small enough and efficiently checkable certificate always ...

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
Why are so few natural candidates for NP-intermediate status?
7 votes

Here is a fairy tale about the Goldilocks structure of NP-intermediate problems. (Warning: this story may be a useful fallacy to generate and test potential hypotheses, but is not meant to be ...

View answer
Justifying asymptotic worst-case analysis to scientists
7 votes

My personal (and biased) take is that asymptotic worst-case analysis is a historical stepping stone to more practically useful kinds of analysis. It therefore seems hard to justify to practitioners. ...

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
Questions about special types of partial assignments
1 votes

Regarding your second and third questions, you want to know if there is a name for a partial assignment that is guaranteed not to be a nogood, and which will generate only satisfying assignments when ...

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
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
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
Examples of hardness phase transitions
10 votes

A particularly striking example of a phase transition is the maximum degree bound for Exactly-$k$-SAT (X$k$SAT), in which each clause contains exactly $k$ distinct literals. The problem flips from ...

View answer