Author |
Topic: NEW PUZZLE - 2SAT --> 2-COL (Read 10762 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
NEW PUZZLE - 2SAT --> 2-COL
« on: Sep 12th, 2002, 10:39pm » |
 Quote  Modify
|
We all (well, almost all) know that SAT is an NP-complete problem. We know further that 3SAT, which is a version of SAT in which EVERY clause has exactly three literals, such as in (x1 + x2 +x3)(x'1 + x'3 + x4), is also NP-complete (here x'1 = NOT x1). The fact that 3SAT is NP-complete can be used to establish that 3COL - the problem of deciding whether a given graph has a 3-colouring - is also NP-complete.
Consider the problem 2SAT, defined similarly as 3SAT. Find out whether this problem is NP-complete, or find a poly-time algorithm to solve it (or both! Then I'd be really impressed). Notice that the corresponding problem 2COL can be easily establihed to be in P. Can you find a reduction from 2SAT to 2COL?
Note: I can't think of a reduction - which I find VERY displeasing aesthetically. 
|
| « Last Edit: Sep 13th, 2002, 11:10pm by william wu » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: NEW PUZZLE - NOT SO EASY
« Reply #1 on: Sep 13th, 2002, 5:56am » |
Quote Modify
|
Man, I remember asking my algorithms gsi the same problem of showing that 2-sat is in P last semester. We thought about it for a while in front of a whiteboard. I can't remember the details! Eventually we translated each clause into a graph widget that uses a concept along the lines of the following:
(~A or ~B) becomes the logical implication A=1 --> B=0
Explanation: Given the clause ~A or ~B, if A is true, that means B must be false for the clause to be satisfiable. Thus we can say that A=1 implies B=0. Likewise we can say B=1 --> A=0, which is just the converse of the above implication.
So the implication becomes a graph component, but I don't remember exactly how. I label one node ~A and another B, then draw an edge between them ... was it directed? Then there is a 2-SAT assignment iff the final graph was strongly connected or something like that ... or was it a 2-colorability argument? ... argh never mind I'll think about it some more.
Well, here's a randomized algorithm for solving 2-sat that apparently runs in P; I heard about it during the first lecture of Karp's randomized algos class this sem:
Code:
choose an initial truth assignment equally at random
// so for n variables, any assignment chosen with probab. 2^-n)
while there exists an unsatisfied clause
choose some unsatisfied clause C equally at random
pick one of the two variables in C equally at random, and flip its truth value
|
|
I have yet to prove to myself that this runs in P ...
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PUZZLE - NOT SO EASY
« Reply #2 on: Sep 13th, 2002, 3:57pm » |
Quote Modify
|
Well, it may solve 2SAT if there IS a solution to the particular instance... but I would like to see a full-blown P-time deterministic decision algorithm, or a proof that 2-SAT is NP-complete.
And please DO e-mail me the reduction in case you find it... if I get an NP-completeness proof from someone, I'll be rich!
|
| « Last Edit: Sep 13th, 2002, 3:59pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: NEW PUZZLE - 2sat --> 2col
« Reply #3 on: Sep 13th, 2002, 10:57pm » |
Quote Modify
|
True the randomized algorithm does not guarantee a solution in the mathematical sense. After you run the while loop for some large number of iterations, the probability of finding the solution should be very high, but not 100%.
Here is what I was trying to say earlier; a reduction from 2 SAT to the problem of finding SCCs in a graph:
Convert each 2SAT clause into two implications. So
(~A or ~B) becomes (A --> ~B), (B --> ~A)
Once you have all these implications, draw a directed graph G with 2n vertices. where n is the number of boolean variables in the 2sat expression. Label n of these vertices (x1 x2 x3 ... xN), and label the others (~x1 ~x2 ~x3 .... ~xN). Then use the implication arrows constructed earlier to draw directed edges connecting the vertices.
An example graphic I made:
There exists a satisfying 2SAT assignment iff no vertex is in a cycle with its complement. When we see a cycle in the graph, all the vertices in the cycle must be set to true. If a vertex and its complement are in the same cycle, that's like saying (X && ~X) == true, which is not possible. So this comes down to finding the strongly connected components of a graph, and making sure that each vertex is not in the same SCC as its complement.
Finding SCCs can be done in about 2*O(V+E) time as follows: Given a directed graph G, construct a graph G' which reverses all the arrows of G. 1) Run DFS on G', keeping track of postvisit times for each vertex. 2) Run DFS on G, labelling connected components, and processing vertices in order of decreasing postvisit values found in step 1).
So we can determine if a 2SAT expression is satisfiable in polynomial time. Now we can also construct a satisfying expression in polytime, I think. All vertices in an SCC must be set to true. Vertices not in SCCs could have many possible valid assignments; to make life easier we could set the root vertex (highest in topological order) in a non-cyclic path of implications to be false, and set all the others to be true (reasoning: in the statement A -> B -> C -> ... -> Z, if A is false, you can't conclude anything about the values of B through Z).
I realize this wasn't a formal reduction, but intuitively I think it works. So 2-SAT can be solved in linear time, and it isn't NP-complete, rats
I think I see how this reduction relates to 2-colorability. I'm saying that a vertex and its complement cannot be in the same cycle, because then they'd have the same truth value and that's impossible. So for 2-colorability, the vertices to variables (x1 x2 x3 ... xN) must have a different color from their complements (~x1 ~x2 ~x3 .... xN). Let's see, we start by drawing edges connecting x1 to ~x1, x2 to ~x2, etc ... hmm still haven't solved the original problem ... do we just need to tweak the implication graph a little?
P.S. BTW I changed the title of the thread from "not so easy" to "2sat --> 2-col"
|
| « Last Edit: Sep 13th, 2002, 11:48pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: NEW PUZZLE - NOT SO EASY
« Reply #4 on: Sep 13th, 2002, 11:09pm » |
Quote Modify
|
... trying to finish off other problems on my mind:
EXPECTED ITERATIONS TILL 2-SAT RANDOM LOCAL SEARCH STOPS =========================================================
Let n = number of boolean variables
Let S(k) = expected number of iters till all n variables in our truth assignment match the real solution, given that k vars already match
CONDITIONAL EXPECTATION RECURRENCE
Eq. 1) S(k) = (0.5) (S(k+1) + 1) + (0.5) (S(k-1) + 1)
for 0<k<n
Eq. 2) S(n) = 0 // base cases
Eq. 3) S(0) = S(1) + 1
Explanation:
1) k variables match right now. k<n. So I invert the value assigned to one variable. This will either result in k+1 or k-1 variables matching. Both cases will occur with probability 0.5. And in both cases, I add "1" to the conditional expectation, to count the iteration I just used.
2) If you have all n vars matched already, you don't need any more iterations to match n vars
3) For most points in the random walk, there are two possible previous states. If k variables are matched right now, then after I invert the value assigned to one variable, either k-1 or k+1 variables will match afterwards. However, if 0 variables are matched right now, inverting the value of a variable will only result in 1 variable matching; it doesn't make sense to say that "-1" variables match.
Now we want to solve for S(0) in closed-form. We could use either the homogeneous + particular solution approach, or Z-transforms; maybe I'll continue this in a later post ...
|
| « Last Edit: Sep 13th, 2002, 11:15pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Yournamehere
Guest
|
|
Re: NEW PUZZLE - 2SAT --> 2-COL
« Reply #5 on: Sep 14th, 2002, 9:49am » |
Quote Modify
 Remove
|
Finding a reduction from 2SAT to 2COL is not going to be easy. You can show that in the general case such a reduction must create disconnected graphs. Since a solution to the reduce problem (i.e. 2COL) must have a translation back to the original problem space (i.e. 2SAT), there must exist an interpretation of the 2-coloring as an assignment of variables.
Note that any connected graph has exactly two 2-colorings (one obtained by "flipping" the other's colors). Now consider the 2SAT problem (a+b). There are three solutions: ab', a'b, and ab. Thus a valid reduction must create a disconnected graph for this 2SAT formula.
Note that it does not matter whether the graph is directed or undirected: there is a 1-1 mapping from the 2-colorings of a directed graph to the 2-colorings of the underlying undirected graph.
The problem with unconnected graphs is that the SCCs of such a graph can be colored independently. There is no 'sharing' of information between the SCCs, as it were. It's clear that a reduction, if one does exist, will look nothing like the standard reduction from 3SAT to 3COL, or the 2SAT reduction to path finding in graphs.
One may note that a 2-coloring of an SCC is uniquely determined by the coloring of a single vertex in the SCC. This may or may not help, though.
As an aside, note that the 2SAT reduction to path finding in graphs yields a simple "greedy" poly-time algorithm, without requiring explicit SCC finding or root finding. Observe that, if a path exists from any vertex u to any other vertex v, there must also be a path from ~v to ~u. Now suppose ~v is unreachable from v. Then one can claim that, after setting v to true, no further consistent variable assignments can ever imply ~v. Suppose this were not true, where some future assignment, say x, implies ~v. So a path exists from x to ~v. But then a path exists from v to ~x, and hence we cannot ever make such an assignment in the future, since we have already set v to true in the first place, and derived ~x.
This means that one can set variables at will, and keep the assignments obtained as long as there is no inconsistency:
while there exists some unassigned variable v {
derive all implications from assigning v=1
if v=0 is not derived {
set v=1 and set all implications thereof
}
else {
return UNSAT
}
}
return SAT, with variable assignments determined
"Deriving implications" is basically a DFS algorithm, hence polynomial running time. You can even show that, even though DFS may be called several times, no edge is ever visited more than once over all DFS calls, so the total running time is O(V+E).
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PUZZLE - 2SAT --> 2-COL
« Reply #6 on: Sep 14th, 2002, 7:51pm » |
Quote Modify
|
BEAUTIFUL reduction, Will. Really. And great analysis too, Yournamehere (I'll change this once you register). But...
I have it! I have it! The 2SAT -> 2COL reduction! Eureka!
By the way, shame on you, Will, spoiling the puzzle for everyone! Now they know it isn't NP-complete...
I don't want to give too much away, but the reduction I found isn't the typical kind I've seen. I give three hints.
1) The graph is not directed;
2) Don't assume that the same vertex must be assigned to every appearance of a variable;
3) Don't assume that solving 2COL just once will give you the answer to 2SAT.
The 2COL argument is much more elegant than my previous one, which was anything except clear, though it kind of used Yournamehere's idea of implications. HE(SHE) fleshed it out beautifully.
About the randomized 2SAT, I'll have to dig up somewhere what the hell a Z-transform is... I'm not that good with recursive sequences, just know a few generating function tricks. But I'll take a shot at proving it's in average-P. I love you guys. You really get my brain working.
|
| « Last Edit: Sep 14th, 2002, 8:01pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Yournamehere
Guest
|
|
Re: NEW PUZZLE - 2SAT --> 2-COL
« Reply #7 on: Sep 15th, 2002, 12:28pm » |
Quote Modify
Remove
|
Here is a "reduction" of 2SAT to 2COL, given 2SAT problem instance X:
if X is satisfiable
return K2
else
return K3
where K2 and K3 are the complete graphs on 2 and 3 vertices, respectively. This "reduction" runs in P-time, since we can determine if X is satisfiable in P-time.
I say "reduction" in quotes because I am not sure this is actually a reduction. There is no way to obtain a solution to the 2SAT problem given a solution to the 2COL problem. But I just took a look at the definition of reducibility (in Cormen, Leiserson and Rivest), and they phrase it simply as a language problem, which the above certainly satisfies. So perhaps my notion of an inverse mapping (from solutions of 2COL back to solutions of 2SAT) is not necessary.
Here is another reduction, which (perhaps only partly) avoids the above problem. The idea is to encode the 2SAT problem as a graph, then recover the SAT formula to dervive a variable assignment:
if X is not satisfiable
return K3
else
generate a graph G with two vertices, ONE and ZERO
add edge from ZERO to ONE
for every pair of literals (x,y) add a vertex to G corresponding to (x,y)
add an edge from every (x,y) to ONE
foreach clause (a+b) in the 2SAT formula
delete edge from (a,b) to ONE and add edge from (a,b) to ZERO
return G
If X is satisfiable, G is 2-colorable, since G contains no cycles, and if X is not satisfiable, the returned graph is K3 which is not 2-colorable. The reduction runs in O(n^2+c), where n is the number of variables and c is the number of clauses in the formula (note that n=O(c) as well).
If one wants to obtain a variable assignment, one takes the solution to the 2COL problem, finds all vertices (x,y) which are colored the same as ONE, and adds the corresponding clause (x+y) to a new SAT formula. This new formula is identical to the original problem, and this procedure runs in O(n^2) time. Then one solves 2SAT on the new formula in polytime, obtaining a variable assignment.
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PUZZLE - 2SAT --> 2-COL
« Reply #8 on: Sep 15th, 2002, 4:05pm » |
Quote Modify
|
I'm in a bit of a rush right now, so I don't have time to really think about your algorithm, Yournamehere (you really SHOULD register). It seems right, though.
What I meant by reducing 2SAT to 2COL certainly did not involve solving 2SAT first! So the "if X is satisfiable" portion of your pseudocode isn't in the spirit of the problem. Don't worry, the reduction I found meets the requirements of not cheating.
I think the correct way to go about this problem is not to assume you know how to solve 2SAT in linear time, since that would pretty much destroy the purpose of reducing it to anything. Suppose you are bothered (much like I was) by the fact that 3SAT reduces to 3COL without actually solving 3SAT but that apparently the same does not hold for 2SAT and 2COL. Now find a nice polynomial reduction. Mine is quite linear, but it may need to solve 2COL for c different graphs in the worst case (c = number of clauses). I'm not sure how to define the complexity of a reduction of this type. Any ideas?
|
| « Last Edit: Sep 15th, 2002, 4:21pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Yournamehere
Guest
|
|
Re: NEW PUZZLE - 2SAT --> 2-COL
« Reply #9 on: Sep 16th, 2002, 12:41pm » |
Quote Modify
Remove
|
on Sep 15th, 2002, 4:05pm, Pietro K.C. wrote:| Mine is quite linear, but it may need to solve 2COL for c different graphs in the worst case (c = number of clauses). I'm not sure how to define the complexity of a reduction of this type. Any ideas? |
|
You can generate a graph which is the union of your c candidate graphs, taken as separate (unconnected) components. Running 2COL on the combined graph effectively runs 2COL on each component individually, since they are not connected. If c subgraphs is a worst case scenario, you can simply ignore the coloring results for some of the components, based on the coloring of the other components.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
 |
Re: NEW PUZZLE - 2SAT --> 2-COL
« Reply #10 on: Sep 22nd, 2002, 9:59pm » |
Quote Modify
|
Disturbing disturbing. I can't seem to solve the 2-SAT random local search recurrence. I've been teaching myself TeX, so as a good exercise I typed up my attempt at solving the recurrence using the homogeneous + particular solutions method; maybe someone can tell me where I erred:
PDF format: http://www.ocf.berkeley.edu/~wwu/papers/rand2satRecurrence.pdf
PS format: http://www.ocf.berkeley.edu/~wwu/papers/rand2satRecurrence.ps
I also prefaced my work with background math on how to solve recurrences.
Maybe the problem has to do with the fact that the sequence doesn't go on forever, and that it has initial conditions at its endpoints. What tool do you use to solve these weird bounded sequences?
Pietro: Z-Transforms are the discrete-time equivalents of Laplace Transforms. They map a sequence onto a complex variable plane; formally, given a sequence x[n],
ZT{x[n]} = X(z) = summation from -inf to inf { x[n]z^-n }
where z is a complex variable. If you want to convolute two discrete time signals, often you can make life easier by transforming both signals into the Z-domain, multiplying them there, and then inverse transforming the product to get the convoluted result in the time-domain. (Just like using Fourier Transforms in continuous time to turn convolution work into multiplication.)
Just as Laplace Transforms can be used to solve differential equations easily, Z-Transforms can be used to solve difference equations easily. Unfortunately my ZT approach toward this problem also ran into a dead end.
Thanks for the compliments BTW
Yournamehere: Interesting. I'll study the reduction some more later; only reason I'm doing this recurrence stuff now is because it relates to material that'll probably be on a upcoming quiz this Tuesday ...
|
| « Last Edit: Sep 24th, 2002, 3:44am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Yournamehere
Guest
|
|
Re: NEW PUZZLE - 2SAT --> 2-COL
« Reply #11 on: Sep 23rd, 2002, 6:23pm » |
Quote Modify
Remove
|
Though I haven't sat down to figure out what's wrong with your attempt, I think this might be simpler:
Given
S(k) = 0.5 S(k-1) + 0.5 S(k+1) +1
S(N) = 0
S(0) = S(1) + 1
Then
S(i+1) - S(i) = S(i) - S(i-1) - 2
= [S(i-1) - S(i-2) - 2] - 2
= S(1) - S(0) - 2i
= -2i -1
S(i) = -2i -1 + S(i-1)
= -2i -1 + [-2(i-1) -1 + S(i-2)]
= -2(i+(i-1)+...+1) -i + S(0)
= -i(i+1) -i + S(0)
= -i^2 - 2i + S(0)
S(N) = -N^2 - 2N + S(0)
S(0) = N^2 + 2N
Note that there is an assumption in the formulation (that of p=0.5 for both moving towards and moving away from a SAT solution) that isn't really true, but one can argue that the probability is certainly better than this, so the above analysis gives a worst-case bound that might not be tight.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: NEW PUZZLE - 2SAT --> 2-COL
« Reply #12 on: Sep 23rd, 2002, 6:57pm » |
Quote Modify
Remove
|
William:
In your particular solution analysis, you're missing
the factors of 0.5: S(k) = 0.5 S(k+1) + 0.5 S(k-1) + 1. The n^2 disappears once you handle this.
Also, for the solution to the homogeneous version, you need to account for the multiplicity of the root, so that a solution is of the form An+B, rather than just a constant.
Picking nits, in the second line of the particular solution equations, where you expand (n+1)^2 and (n-1)^2, you're missing a +1.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: NEW PUZZLE - 2SAT --> 2-COL
« Reply #14 on: Sep 23rd, 2002, 11:06pm » |
Quote Modify
Remove
|
Well, you have
S(0) = S(1) + 1
a_1 * 0 + a_2 - 0^2 = a_1 * 1 + a_2 - 1^2 + 1
so a_1 = 0 and a_2 = n^2, and S(0) = n^2.
This is at odds with my solution above, though. It turns out I also made an error: my statement
S(i) = -2i -1 + S(i-1)
has an incorrect sign, and should have been
S(i) = -2i +1 + S(i-1)
Percolating the fix through the solution gives the same result as you have: S(i) = N^2 - i^2, and S(0) = N^2.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: NEW PUZZLE - 2SAT --> 2-COL
« Reply #15 on: Sep 24th, 2002, 1:21am » |
Quote Modify
|
Whoohoo! Finally resolved. Thanks for the help.
Incidentally, when I asked Dr. Karp about solving this recurrence yesterday, he suggested something like your approach as well.
|
| « Last Edit: Sep 24th, 2002, 1:49am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print