Timeline for Prove NP-completeness of deciding satisfiability of monotone boolean formula
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 28, 2024 at 6:10 | history | edited | D.W.♦ | CC BY-SA 4.0 | edited body |
| Aug 28, 2017 at 11:33 | comment | added | rus9384 | @HaskellFun, I thought about this also. Vertex cover is the same as monotone Min-W2SAT. | |
| Aug 28, 2017 at 10:17 | comment | added | Haskell Fun | I think that exactly the same approach works with verticles coverage. | |
| Apr 26, 2013 at 1:48 | comment | added | Luke Mathieson | @nat indeed, the going from vertex cover is also nice because it gives you a formula in 2CNF, which is interesting as 2-SAT is in P, but monotone WSAT with 2CNF formulae is NP-complete. Coincidentally, you can also get antimonotone results (where every variable is negated, but you want at least $k$ true variables) from Clique/Independent set. If you're particularly keen, you may want to look into Parameterized Complexity, where these sort of satisfiability problems play central roles. | |
| Apr 26, 2013 at 1:21 | comment | added | nat | I'm also seeing that we can also reduce the vertex cover down to the monotone boolean formula. | |
| Apr 26, 2013 at 0:57 | vote | accept | nat | ||
| Apr 26, 2013 at 0:56 | comment | added | nat | Wow this makes so much more sense, thank you! I think I was definitely caught up in trying to reduce SAT down to the monotone boolean formula. | |
| Apr 26, 2013 at 0:29 | history | answered | Luke Mathieson | CC BY-SA 3.0 |