Timeline for Satisfiability of general Boolean formulas with at most two occurrences per variable
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2009 at 2:35 | comment | added | David Eppstein | A simpler but similar argument: if you had a gate with three inputs u,v,w that computed the function (u ⋀ v ⋀ w) ⋁ (¬u ⋀ ¬v ⋀ ¬w) you could use it to split one variable u into two equivalent variables v and w and get around the two-occurrences-per-variable limitation. | |
| Dec 22, 2009 at 2:34 | comment | added | Ryan Williams | Very nice observation. This suggests another question: which collections of basis gates make the problem easy, and which make the problem hard? My intuition is that the choice of basis gates should make a huge difference. | |
| Dec 22, 2009 at 2:24 | history | answered | David E Speyer | CC BY-SA 2.5 |