Is the following true or false? Why?

Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.

  • 3
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just answering homework-style exercises for you is unlikely to really help you. Think about why you can't answer this question yourself, and ask a question about that. $\endgroup$ – David Richerby Feb 27 '19 at 19:45
  • $\begingroup$ I think the complement from tautology is element NP (I am not really sure if it is true, but tautology is element co-np). I am not sure, if the reduction is true, because X is just NP hard und not NP-complete, but I think it is true. By the way, it is not my homework...just trying to understand it $\endgroup$ – user101036 Feb 27 '19 at 20:00

The statement is: If a problem $P$ is $\mathbf{NP}$-hard, then there is a reduction from $\text{FALSIFIABLE}$ to $P$. ($\text{FALSIFIABLE}$ being the set of formulas for which there is an assignment which makes the formula false; this is trivially equal to the complement of $\text{TAUT}$.)

This statement is correct.

Why? Simply because $\text{FALSIFIABLE}$ is $\mathbf{NP}$-complete. You can prove this exactly the same way $\text{SAT}$ is proven to be $\mathbf{NP}$-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 duality principle of Boolean algebra.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy