Talk:co-NP-complete

Positive boolean formula

This article mentions the problem of determining whether a "positive boolean formula", but doesn't explain what that means. ~ Booya ^Bazooka 03:32, 16 September 2011 (UTC)

Actually, I believe the part about positive Boolean formulas is wrong. Unless I'm mistaken, it is quite simple to determine in polynomial time whether a positive Boolen formula is a tautology (and under the assumption P≠NP, this would mean it would not be co-NP-complete). You simply set all variables to false and evaluate the formula. If the result is false, naturally it is not a tautology. If it is true, then, by the definition of a positive Boolean formula (and positive Boolean function), it will remain true if you change one or more variables to true. Therefore, it will be true for any pattern of truth values, and thus is a tautology. (For more on positive Boolean functions and formulas, I recommend the excellent book on Boolean functions by Crama & Hammer. The first part is available online, and discusses positive functions.) If this is correct, of course the text should be modified, to omit this part. Otherwise, the text should ideally contain a reference or basic argument to show that it's true. Mlhetland (talk) 19:35, 27 January 2016 (UTC)

An addendum: A Boolean function could be true for all inputs (essentially a tautology), but the only way to implement that with a Boolean formula would be for it to be empty, I guess? So no "normal" positive Boolean formula would be a tautology, as setting all variables to false would always make the formula false. So in a sense this isn't even a "problem" that could be co-NP-complete – it's just a fact about positive Boolean formulas (i.e., that they are not tautologies). Or…? --Mlhetland (talk) 20:17, 27 January 2016 (UTC)