Timeline for Improving Cook's generic reduction for Clique to SAT?
Current License: CC BY-SA 3.0
8 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Dec 8, 2015 at 14:34 | vote | accept | András Salamon | ||
Dec 7, 2015 at 6:20 | answer | added | D.W. | timeline score: 10 | |
Dec 5, 2015 at 21:35 | comment | added | András Salamon | @JoeBebel: with $k\log n$ space it is even possible to output a SAT instance with $k\log n$ variables, the solutions to which are all the locations of $k$-cliques in the graph. For each potential clique, one outputs a clause forbidding that $k$-clique if it is not present. This captures the solutions precisely, a one-one reduction, so answers Kaveh's question, but just as with your suggestion, solving the instance before deciding on how to reduce it seems like a cheat too far. | |
Dec 5, 2015 at 6:12 | comment | added | Joe Bebel | Do you want a reduction that runs in log space as well? Because as you point out, $k$-clique can be solved in polynomial time for constant $k$, so a polynomial time reduction can actually check for a $k$-clique and then output a constant sized SAT instance. | |
Dec 4, 2015 at 20:24 | history | tweeted | twitter.com/StackCSTheory/status/672874256762601472 | ||
Dec 4, 2015 at 19:56 | comment | added | David Eppstein | See a somewhat-related question mathoverflow.net/q/224898/440 on MathOverflow, in which the small size of a quantified Boolean formula for $k$-clique translates directly into the slow convergence rate of the 0-1 law for random graphs. The question already contains a formula of quadratic size; the accepted answer gives a linear-size formula that implies the existence of a $k$-clique, but that might be false even when a clique exists. | |
Dec 4, 2015 at 17:48 | history | edited | András Salamon | CC BY-SA 3.0 |
fix typo
|
Dec 4, 2015 at 17:18 | history | asked | András Salamon | CC BY-SA 3.0 |