Skip to main content
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