# Is embedding a solution feasible for SAT?

I am interested in "hard" individual instances of NP-complete problems.

Ryan Williams discussed the SAT0 problem at Richard Lipton's blog. SAT0 asks whether a SAT instance has the specific solution consisting of all 0's. This got me thinking about constructing SAT instances that are likely to be "hard".

Consider a SAT instance $\phi$ with $m$ clauses and $n$ variables, where $\alpha = m/n$ is "large enough", in the sense that it falls into the region beyond the phase transition, where nearly all instances are unsatisfiable. Let $x$ be a random assignment to the values of $\phi$.

Is it possible to modify $\phi$ to obtain a new instance $\phi|x$, so that $\phi|x$ is "largely similar" to $\phi$, but so that $x$ is a satisfying assigment for $\phi|x$?

For instance, one could try to add to each clause a randomly chosen literal from the solution, that does not already occur in the clause. This will guarantee that $x$ is a solution.

Or is this hopeless, leading to a fast algorithm for finding the "hidden" solution, along the lines of the following recent paper?

I am aware of the discussion by Cook and Mitchell and work they reference. However, I couldn't find anything about what happens to the structure of a formula when one tries to explicitly embed a satisfying assignment into it. If this is folklore, pointers would be very welcome!

• Stephen A. Cook and David G. Mitchell, Finding Hard Instances of the Satisfiability Problem: A Survey, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 35 1–17, AMS, ISBN 0-8218-0479-0, 1997. (PS)

You can take any formula $\varphi$ and change it to the formula $\varphi \vee \psi_x$ where $\psi_x$ is a "hard" SAT instance whose only solution is $x$. One way to construct such a formula is using cryptography: if $f:\{0,1\}^n\rightarrow \{0,1\}^n$ is a one-way permutation and we choose $x$ at random and set $y=f(x)$, then one can convert $y$ into a SAT formula such that $x$ is its only solution and thus finding $x$ corresponds to inverting $f$. (We need for this $x$ to be random, but this something similar is anyway assumed if we think finding $x$ should be hard.)

• Ah, $\phi \lor \psi_x$ has polynomial size in $\phi$ and $\psi_x$. Thanks! – András Salamon Sep 19 '10 at 22:54

If I correctly understand the very core of your question, you want to take a relatively easy instance (since you put yourself in an area where $\frac{m}{n}> 4.3$), and transform it into a hard one by embedding a solution. I doubt that this would work.

Experimental data suggest that, when constructing a random instance "around" a predefined solution $x$, such instance will be easier than usual (compared to similar instances having the same $n$ and $m$). It's like if the hidden solution helps the SAT solver, guiding it through the search space. Normally, to construct such an instance, we generate random clauses as usual (e.g. choosing $k$ literals at random and negating each of them with probability $p = \frac{1}{2}$) but we discard those clauses which are not satisfied by our hidden solution $x$. For what concerns your approach of constructing $\phi|x$ from and hard instance $\phi$: I've never tried that, but I "feel" that $\phi|x$ will become easier, if not trivial. I believe that doing that would augment the hit count of $x$'s literals (the hit count of a literal $l$ is the number of occurrences of $l$ in a given formula), and that this would drive the SAT solver to the target. Maybe the solution spaces of $\phi$ and $\phi|x$ would be similar (if not almost identical), as happens in Ryan Williams' example of SAT0 (almost identical solution spaces, but completely different hardness). Did you try your approach in practice? It would be interesting to see how the same SAT solver behaves on $\phi$ and on $\phi|x$.

EDIT 1 (23rd Sep 2010): After thinking a little bit more, I feel that actually $\phi|x$ solution space would be very different than $\phi$'s. You are adding a literal to each clause, so you're giving more degree of freedom to such clauses (i.e. each clause has more chance to be satisfied): probably the resulting solution space would be massively transformed.

EDIT 2 (1st Oct 2010): I've thought about the following very simple and not original idea. Given an initial instance $\phi$ and an assignment $x$:

1. Remove from $\phi$ all those clauses unsatisfied by $x$. This will enlarge the solution space, and should embed $x$ in it.

2. Suppose you removed $m_x$ clauses. Now randomly add $m_x$ new clauses, taking care that they are not unsatisfied by $x$ (this will narrow the solution space again, but without pushing $x$ out of it).

I don't know if this will work or not. I didn't try it, yet. More precisely, I'm not sure if Step 1 always manages to embed $x$ in the solution space (maybe $x$ is ruled out by some combination of clauses, even if each of them is not unsatisfied by $x$?).

• Thanks for the comments, I agree that the solution space would be changed. As indicated in the question, I want to know whether there is a way to modify the formula to hide a solution. Adding the literals to each clause is meant as an existence proof that one can add the solution to the formula. I did not mean to suggest that this is the only, best, or even a good method. – András Salamon Sep 17 '10 at 12:57
• You're welcome, Andras. Yes, solution $x$ can certainly be added using your method. If you want that $\phi|x$'s solution space is exactly equal to $\phi$ solution space plus just that solution $x$, I think this is hard to obtain. On the other hand, if you're willing to accept that many other solutions will be added, your strategy is OK. – Giorgio Camerani Sep 17 '10 at 14:10
• Ideally one wants a polytime-computable method that doesn't change the solution space "too much"... – András Salamon Sep 18 '10 at 11:15
• It would be interesting to check whether the $n^{3\log\ n}$ algorithm mentioned by Feige for planted cliques still works for any of these planted solutions. – András Salamon Oct 2 '10 at 22:46
• @Walter: The reason I say it would be interesting to investigate the simple "find a $3 \log n$-clique" algorithm, is that the easiest reduction of SAT to CLIQUE requires an $n$-clique in a graph with $2n$ vertices. Either bridging this gap between $n$ and $3\log n$, or showing it can't be bridged, would be interesting. – András Salamon Oct 3 '10 at 15:30

The best way to generate hard instances of NP-complete problems that I'm aware of is to use the Cook mapping to reduce carefully selected instances of certain other hard NP problems (such as the discrete logarithm problem or integer factorization) to SAT. These are the same "hard problems" that are used by mathematicians to ensure cryptographic security in protocols such as RSA and Diffie-Hellman.

• References, please? – gphilip Sep 24 '10 at 3:52
• not sure why the downvote for this answer. whoever did it should explain. – Suresh Venkat Sep 24 '10 at 5:58