Mathematics Asked by rasul_rza24 on December 18, 2020

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.

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**.

Answered by Jsevillamol on December 18, 2020

0 Asked on November 14, 2021 by joey-cho

convex analysis elementary set theory matrices permutation matrices

3 Asked on November 14, 2021 by giuliano-cantina

alternative proof functional inequalities inequality real analysis solution verification

1 Asked on November 14, 2021

1 Asked on November 14, 2021

2 Asked on November 14, 2021 by peter-petrov

diophantine equations elementary number theory number theory

2 Asked on November 14, 2021 by teabx

1 Asked on November 14, 2021

2 Asked on November 14, 2021 by air-mike

0 Asked on November 14, 2021

algebraic geometry birational geometry commutative algebra derived functors schemes

3 Asked on November 14, 2021 by shreedhar-bhat

2 Asked on November 14, 2021 by pwelb

2 Asked on November 12, 2021 by ben-schneider

2 Asked on November 12, 2021 by pavel-fedotov

1 Asked on November 12, 2021

1 Asked on November 12, 2021 by daniel-sidorkin

1 Asked on November 12, 2021 by user745578

functional analysis hilbert spaces normal operator operator theory

0 Asked on November 12, 2021 by rex-wang

0 Asked on November 12, 2021 by tempuserperson

1 Asked on November 12, 2021 by fratsourced

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP