Timeline for Satisfiability of general Boolean formulas with at most two occurrences per variable
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2009 at 6:05 | comment | added | Theo Johnson-Freyd | +1 for detailed intro | |
| Dec 22, 2009 at 4:17 | history | edited | Ryan Williams | CC BY-SA 2.5 |
added 103 characters in body
|
| Dec 22, 2009 at 4:15 | vote | accept | Ryan Williams | ||
| Dec 22, 2009 at 3:54 | answer | added | Ryan O'Donnell | timeline score: 21 | |
| Dec 22, 2009 at 2:24 | answer | added | David E Speyer | timeline score: 4 | |
| Dec 22, 2009 at 2:02 | history | edited | Ryan Williams | CC BY-SA 2.5 |
added another example for clarity
|
| Dec 22, 2009 at 0:14 | answer | added | David Eppstein | timeline score: 1 | |
| Dec 21, 2009 at 22:36 | comment | added | Boris Bukh | 2-SAT is a different problem where each clause contains at most two literals. | |
| Dec 21, 2009 at 22:36 | comment | added | Ryan Williams | That is not my question! 2-SAT is conjunctive normal form with two variables per clause. | |
| Dec 21, 2009 at 22:30 | comment | added | Qiaochu Yuan | 2-SAT is in P. See en.wikipedia.org/wiki/2-satisfiability . | |
| Dec 21, 2009 at 22:29 | history | asked | Ryan Williams | CC BY-SA 2.5 |