Timeline for Reducing optimization problem to decision problem
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 22, 2015 at 14:01 | comment | added | hengxin | What if there are more than one max-cut solutions in the original graph? For example, consider the complete graph with 4 nodes. | |
| Apr 20, 2014 at 21:56 | vote | accept | so.very.tired | ||
| Apr 20, 2014 at 21:31 | comment | added | user2566092 | @so.very.tired Yes that's exactly the clause you should add if it's (1,0) or (0,1). And 2-sat has a polynomial time solution (even linear time solution), see. e.g. en.wikipedia.org/wiki/2-satisfiability | |
| Apr 20, 2014 at 21:25 | comment | added | so.very.tired | And what clauses should I add for if $(x_u,x_v)=(1,0)$ or $(0,1)$? should it be $(\neg x_v\vee \neg x_u)\wedge (x_v\vee x_u)$? | |
| Apr 20, 2014 at 21:09 | comment | added | so.very.tired | Thanks for the help, but isn't the 2-sat problem NP-Complete? How can I find an assignment that satisfies the formula after creating it, in polynomial time? | |
| Apr 20, 2014 at 19:33 | history | edited | user2566092 | CC BY-SA 3.0 |
added 183 characters in body
|
| Apr 20, 2014 at 19:20 | history | answered | user2566092 | CC BY-SA 3.0 |