# P-NP for decision problems

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

## Related Questions

### Is a convex set of permutation matrices $ntimes n$ ($mathbb{P}_{n}cap mathbb{C}$) a singleton?

0  Asked on November 14, 2021 by joey-cho

### Let $0leq a leq b leq 1$. Then we have for all natural numbers $mgeq 2$ the inequality $b^{frac m2}-a^{frac m2} leqfrac m2(b-a)$

3  Asked on November 14, 2021 by giuliano-cantina

### Let $x=begin{bmatrix}3cr4end{bmatrix}$ and $A=begin{bmatrix}0&x^Tcr x&0end{bmatrix}$ is A diagonizable?

1  Asked on November 14, 2021

### Is a directed graph different from a flow graph?

1  Asked on November 14, 2021

### The diophantine equation $m = x^2 + 7y^2$

2  Asked on November 14, 2021 by peter-petrov

### Is there any visual representation on why (certain) trigonometric functions have infinite derivatives.

2  Asked on November 14, 2021 by teabx

### Is $(I circ A – I circ B)$ positive semi-definite if $A$, $B$ and $A – B$ are positive semi-definite?

1  Asked on November 14, 2021

### $f^{*}$ is surjective if and only if $f$ is injective

2  Asked on November 14, 2021 by air-mike

### Rational singularity of Spec, Proj and Spec of localization of a standard graded $2$-dimensional ring

0  Asked on November 14, 2021

### Determine the lie algebra of the subgroup of SO(4)

3  Asked on November 14, 2021 by shreedhar-bhat

### How to use general recursion to generate a set of words?

2  Asked on November 14, 2021 by pwelb

### Calculate Hessian of a “weird” function

2  Asked on November 12, 2021 by ben-schneider

### Find volume under given contraints on the Cartesian plane.

2  Asked on November 12, 2021 by pavel-fedotov

### Equivalence of Classical Nullstellensatz to “Affine schemes have points”

1  Asked on November 12, 2021

### A donut shop sells 12 types of donuts. A manager wants to buy six donuts, one for himself and 5 for his employees.

1  Asked on November 12, 2021 by daniel-sidorkin

### A compact normal operator is diagonalisable.

1  Asked on November 12, 2021 by user745578

### If complex matrices $A$, $B$, $AB-BA$ are nilpotent, show that $A+B$ is nilpotent.

0  Asked on November 12, 2021 by rex-wang

### Integral with an index

1  Asked on November 12, 2021

### How do I find the probability distribution of a dependent variable given the probability distributions of its independent variables?

0  Asked on November 12, 2021 by tempuserperson

### Show that $sup_{k geq 1 }inf_{n geq k} a_n = inf_{k geq 1} sup_{n geq k} a_n$ for an alternating sequence

1  Asked on November 12, 2021 by fratsourced