Timeline for Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 16, 2022 at 21:34 | vote | accept | Daniel Donnelly | ||
| Aug 16, 2022 at 20:59 | comment | added | Yuval Filmus | For the proof of the claim, use the fact that majority on three inputs is a polymorphism of width-2 clauses but not of width-3 clauses. | |
| Aug 16, 2022 at 18:36 | history | edited | John L. | CC BY-SA 4.0 |
Added a strong claim.
|
| Aug 16, 2022 at 17:42 | history | edited | John L. | CC BY-SA 4.0 |
All arguments in my previous answer are either ineffective or wrong.
|
| Aug 16, 2022 at 15:11 | history | edited | John L. | CC BY-SA 4.0 |
A more-obvious argument.
|
| Aug 16, 2022 at 14:54 | history | answered | John L. | CC BY-SA 4.0 |