1
$\begingroup$

This is a question on a practice final.

Which of the following statements are true? If it is false, what is the underlying reason behind that?

I. If 3-CNF-SAT is in P, then Clique is also in P.

II. For decision problems $L_{1}, L_{2}$ in NP, if P is not NP, $L_{1}$ is at least as hard as $L_{2}$, and $L_{2}$ is at least as hard as $L_{1}$, then $L_{1}$ and $L_{2}$ are NP-complete.

III. For decision problems $L_{1}, L_{2}$ in NP-complete, if $L_{1}$ is not in P, then $L_{2}$ is also not in P

We are told that only the third statement is True, but there's no explanation why on the key. I have tried to figure this out, and the only conclusion I've come to is:

(I) cannot be true because if A is polynomially reducible to B, this implies B is at least as hard as A, not vice-versa (Not sure if this is a correct conclusion, so feedback on this would be appreciated.)


This is the first time I'm learning about the notion of hardness, so I don't understand most of the technical explanations I've found. Any clarifications on why I, II is incorrect, and why III is correct would be appreciated.

Self study I've done includes reading multiple StackExchange posts, multiple Wiki pages, and the corresponding section in the Cormen book. I just personally understand concepts better if I see different explanations.

$\endgroup$
8
  • $\begingroup$ Do you see why (I) and (III) are almost Identical claims? $\endgroup$ Dec 3, 2020 at 19:32
  • $\begingroup$ I would really appreciate to see complete explanations, especially on the first problem. It seems that reverse direction for first part can be true as well. $\endgroup$ Dec 3, 2020 at 19:33
  • $\begingroup$ Both Clique and 3-CNF-SAT are NP-complete problems. $\endgroup$ Dec 3, 2020 at 19:35
  • $\begingroup$ @BaderAbuRadi But if latter is in P, does it mean clique will also be in P? Please, follow the given asked question. $\endgroup$ Dec 3, 2020 at 19:44
  • 2
    $\begingroup$ Now that you understand what confused you, you can edit the question, and provide an answer for others. $\endgroup$ Dec 3, 2020 at 20:48

1 Answer 1

0
$\begingroup$

You are right about $1$.

For $2$, $L_1$ reduces to $L_2$, means $L_1$ as least as hard as $L_2$. But not vice versa as adding numbers is in $P$ and tower of Hanoi is in $EXP$, so the later is hard but addition does not reduce to tower of Hanoi. Just knowing the hardness does not say much. Hence the statement is false. If it were not the case, then statement $2$ would have been true.

For $L_1, L_2\in NP\;Complete$, as $L_1,L_2\in NP$, $L_1$ reduces to $L_2$ and $L_2$ reduces to $L_1$, according to NP-Complete definition. So, their hardness is same. So, they both belong to the same class. Hence, $L_1\in P\Rightarrow L_2\in P$ and vice versa. So, $3$ is correct.

$\endgroup$

Your Answer

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

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