Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:14:31Z https://cs.stackexchange.com/feeds/question/104926 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/104926 1 Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology? user101036 https://cs.stackexchange.com/users/0 2019-02-27T16:25:26Z 2019-02-28T07:52:40Z <p>Is the following true or false? Why?</p> <p>Let <span class="math-container">$Y$</span> denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of <span class="math-container">$Y \leq_{p} X$</span>.</p> https://cs.stackexchange.com/questions/104926/-/104927#104927 2 Answer by dkaeae for Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology? dkaeae https://cs.stackexchange.com/users/70382 2019-02-27T16:35:14Z 2019-02-27T16:42:38Z <p>The statement is: If a problem <span class="math-container">$P$</span> is <span class="math-container">$\mathbf{NP}$</span>-hard, then there is a reduction from <span class="math-container">$\text{FALSIFIABLE}$</span> to <span class="math-container">$P$</span>. (<span class="math-container">$\text{FALSIFIABLE}$</span> being the set of formulas for which there is an assignment which makes the formula false; this is trivially equal to the complement of <span class="math-container">$\text{TAUT}$</span>.)</p> <p><strong>This statement is correct.</strong></p> <p>Why? Simply because <span class="math-container">$\text{FALSIFIABLE}$</span> is <span class="math-container">$\mathbf{NP}$</span>-complete. You can prove this exactly the same way <span class="math-container">$\text{SAT}$</span> is proven to be <span class="math-container">$\mathbf{NP}$</span>-complete, only inverting the truth values "true" and "false" (i.e., instead of searching for an assignment which makes the formula true, you search for an assignment which makes the formula false). This is not at all surprising; it is basically the <a href="https://en.wikipedia.org/wiki/Boolean_algebra#Duality_principle" rel="nofollow noreferrer">duality principle</a> of Boolean algebra.</p>