Timeline for Show that the SAT Problem for CNF formulas with at most two occurences of each variable can be solved in polynomial time
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 9, 2019 at 18:26 | comment | added | Yuval Filmus | Right, equisatisfiability is the correct notion. | |
| May 9, 2019 at 17:55 | comment | added | GMA | (Other than that your explanation is fine though.) | |
| May 9, 2019 at 17:55 | comment | added | GMA | It's not true that "x or C" and "not-x or D" are logically equivalent to "C or D". E.g. the assignment x=true, C=false, D=true makes the first pair of formulas true, but the second false. It's more accurate to say that the two are equisatisfiable, i.e. "(x or C) and (not-x or D)" is satisfiable iff "C or D" is. | |
| Jan 14, 2018 at 17:15 | vote | accept | Eden Hassard | ||
| Jan 14, 2018 at 16:48 | comment | added | Yuval Filmus | Don't forget to upvote (if possible) and accept the answer if you think that it is useful and answers your question. | |
| Jan 14, 2018 at 16:48 | comment | added | Yuval Filmus | It's a pretty standard exercise - these things usually look simple in hindsight, though they can be hard to think of if you've never seen them before. | |
| Jan 14, 2018 at 15:43 | comment | added | Eden Hassard | Thank you so much. This solution seems so simple, I feel so dumb right now. Anyways, thanks, I appreciate it a lot. | |
| Jan 14, 2018 at 15:23 | history | answered | Yuval Filmus | CC BY-SA 3.0 |