Timeline for For what k is MAX-2-SAT-k NP-complete?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 12, 2014 at 12:38 | comment | added | Artem Kaznatcheev♦ | I wonder if the problem is also still PLS-complete. | |
| Jan 8, 2014 at 21:50 | history | edited | Marzio De Biasi | CC BY-SA 3.0 |
added 47 characters in body
|
| Jan 8, 2014 at 21:50 | vote | accept | domotorp | ||
| Jan 8, 2014 at 21:46 | comment | added | Marzio De Biasi | @domotorp: you are right :-S ... "3-NAE-OCC MAX 2SAT"! :-) ... I'll edit the answer | |
| Jan 8, 2014 at 21:40 | comment | added | domotorp | Nice, just what I wanted! Before I accept, why could we not reduce it? If a variable appeared only pos or neg, then we can fix its value, so we can suppose there are no such variables, right? | |
| Jan 8, 2014 at 21:24 | history | edited | Marzio De Biasi | CC BY-SA 3.0 |
added 2 characters in body
|
| Jan 8, 2014 at 21:18 | history | answered | Marzio De Biasi | CC BY-SA 3.0 |