0
$\begingroup$

On introduction to the theory of computation - 2nd edition by Michael Sipser, there's this question with the solution:

Question: "7.31: In the following solitaire game, you are given an m x m board. On each of the m² positions lies either a blue stone, a red stone, or nothing at all. You play by removing stones from the board so that each column contains only stones of a single color and each row contains at least one stone. You win if you achieve this objective. Winning may or may not be possible, depending upon the initial configuration. Let SOLITAIRE = {| is a winnable game configuration}. Prove that SOLITAIRE is NP-complete."

Solution: " First, SOLITAIRE E NP because we can verify that a solution works, in polynomial time. Second, we show that 3SAT is reductible in polynomial time to SOLITAIRE. Given Phi with m variables x1, ..., xm and k clauses c1, ..., ck, construct the following k x m game G. We assume that Phi has no clauses that contain both xi and ¬xi, because such clauses may be removed without affecting satisfiability.
If xi is in clause cj, put a blue stone on the row cj, column xi. if ¬xi is in clause cj, put a red stone on the row cj, column xi. We can make the board square by repeating a row or adding a blank column as necessary without affecting solvability. We show that Phi is satisfiable iff G has a solution.
(->) Take a satisfying assignment. If xi is true (false), remove the red(blue), stones from the corresponding column. So, stones corresponding to true literals remain. Because every clause has a true literal, every row has a stone.
(<-) Take a game solution. If the red(blue) stones were removed from a column, set the corresponding variable true (false). Every row has a stone remaining, so every clause has a true literal. Therefore phi is satisfied."

Why is it reduced to 3-SAT instead of k-SAT? the board is m x m so every line is associated with a clause and there can be more or less than three stones (literals) on each line (clause). I see this way:

for instance m = 6:

 x1 x2 x3 x4 x5 x6
|R |B |R |  |R |  | c1 = (¬x1 v  x2 v ¬x3 v ¬x5)
|B |B |R |R |  |  | c2 = ( x1 v  x2 v ¬x3 v ¬x4)
|  |R |  |B |  |  | c3 = (¬x2 v  x4)
|  |  |R |  |B |  | c4 = (¬x3 v  x5)
|  |R |  |  |  |B | c5 = (¬x2 v  x6)
|R |B |  |B |B |B | c6 = (¬x1 v  x2 v  x4 v  x5 v  x6)

I know that I can reduce 3-SAT to k-SAT by repeating a literal (eg. (x1 v x2) = (x1 v x2 v x1)) or by dividing a clause into two or more (eg. (x1 v x2 v x3 v x4 v x5) = (x1 v x2 v ¬s1) and (¬s2 v x3 v x4) and (s1 v s2 v x5)). Am I seeing this wrong?

Sorry for bad formatting, never really posted anything on forums.

$\endgroup$
0
$\begingroup$

The entire solitaire game is of course nothing more or less than a vivid description of the CNF-SAT problem in general -- (except the the boring case where a clause contains the same variable both directly and negated would need to be represented with both a red and a blue stone in the same square, but such clauses are trivial anyway).

Therefore one might as well have reduced from CNF-SAT instead of 3SAT. Only the author of the text you're quoting can know why he didn't choose to that. But a guess would be that he's treating 3CNF-SAT as the prototypical NP-complete problem -- that he expects it to be less confusing for a reader to see a reduction from 3SAT because then you won't have to wonder why he didn't use 3SAT when that would be just as easy.

This expectation seems not to have worked well for you, but I think you can be reasonably sure that's all there is to it: There are two variants of the argument that both work; the author picked the one he thought would confuse you the least, but guessed wrong.

$\endgroup$
  • $\begingroup$ Thank you for your answer :D But I still don't understand how he proves it with 3-sat since you can have more than 3 stones on a row. $\endgroup$ – Guilherme Corrêa Jun 27 '16 at 21:47
  • $\begingroup$ @user350369: Nobody says you have to have more than 3 stones in a row. When you reduce from 3SAT to the Solitaire game you start out with a 3CNF formula that someone gave you, and you're supposed to produce a Solitaire position whose correct answer is the same as the 3SAT instance. The reduction doesn't have to be able to produce every possible starting Solitaire position, as long as for every 3CNF formula it finds some matching Solitaire instance. $\endgroup$ – hmakholm left over Monica Jun 27 '16 at 22:00
  • $\begingroup$ @user350369: In general it looks like you're having trouble distinguishing which problems you're reducing to and from -- several of the times in your question where you say "reduce to" it looks like you really mean "reduce from" and vice versa. Perhaps you ought to go back to the definitions and make sure you understand completely what is what here. $\endgroup$ – hmakholm left over Monica Jun 27 '16 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.