P-NP for decision problems

Question

The final quiz problem asked whether the statement
For decision problems L1, L2 in NP, if P is not NP, L1 is at least as hard as L2, and L2 is at least as hard as L1, then L1 and L2 are NP-complete
is true or false. In fact, it seemed to me even hard to provide a counterexample for this statement, since this is intuitively a wrong assumption, but hard to prove it. I would be welcomed to know your any ideas for this problem.

Jsevillamol · Answer

It could be that $L1$ and $L2$ are in $P$ (since $Psubset NP$).
Then both are equally hard but neither is $NP$-complete (since $P ne NP$ by assumption).
Hence the statement is false.

P-NP for decision problems

One Answer

Add your own answers!

Ask a Question