0
$\begingroup$

enter image description here

Why is the above statement true? my understanding is:

(1)3SAT reduces to X implies X is NP-complete or harder.

(2)Set Cover reduces to X implies X is neither NP-Complete nor harder.

This contradiction gets me a bit lost as to why the conjunction of 1 and 2 implies that X exists in P. I'm hoping someone can explain this to me. Note: both 3SAT and Set Cover are NP-Complete.

$\endgroup$
2
  • $\begingroup$ What is $\le_P^m$ and what is $\nleq_P^m$? $\endgroup$
    – xskxzr
    Jan 18, 2020 at 10:21
  • $\begingroup$ The statement "3-SAT polynomially reduces to $X$ and set cover does not polynomially reduce to $X$" is a contradiction. $\endgroup$
    – Laakeri
    Jan 18, 2020 at 11:55

1 Answer 1

1
$\begingroup$

Your understanding is correct, but the takeaway here is that assuming the contradictions implies that anything can be true. Perhaps reading up on some logic rules might help, the important rule here is that $\bot$ (false) implies everything. Here is a little proof of the problem just for fun:

We know that both 3-SAT and Set Cover are NP-Complete problems. Now, assume that 3-SAT $\leq^{m}_P$ X and that Set Cover $\nleq^{m}_P$ X. We want to show that X $\in$ P.

Since both 3-SAT and Set Cover are NP-Complete problems, we know that Set Cover $\leq^{m}_P$ 3-SAT. We also know that 3-SAT $\leq^{m}_P$ X. By the transitive property of reductions, we know that Set Cover $\leq^{m}_P$ X. Now we know that Set Cover $\leq^{m}_P$ X and Set Cover $\nleq^{m}_P$ X, which is a contradiction. Since false implies everything, we can say that X $\in$ P. (In fact we can also say that pigs can fly faster than superman can)

Q.E.D.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.