Timeline for Proving 2P2N SAT is NP-Complete
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 21, 2014 at 12:36 | comment | added | misberner | I doubt that this would work. First, you cannot prove NP-completeness by reducing 2P2N to 3SAT - you have to do it the other way round (which you do correctly in your description). Furthermore, you cannot add variables with "an identical truth mapping" just like that, as SAT is finding such a truth mapping (among ALL possible). You could encode this in additional clauses, but this requires great care to ensure that with your new clauses you do not violate the 2P2N restriction. | |
| Feb 21, 2014 at 5:21 | history | answered | Alex Chumbley | CC BY-SA 3.0 |