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.

np complete

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

Answered by Jsevillamol on December 18, 2020

P-NP for decision problems

One Answer

Add your own answers!

Related Questions

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

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)$

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

Is a directed graph different from a flow graph?

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

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

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

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

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

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

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

Calculate Hessian of a “weird” function

Find volume under given contraints on the Cartesian plane.

Equivalence of Classical Nullstellensatz to “Affine schemes have points”

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

A compact normal operator is diagonalisable.

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

Integral with an index

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

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

Ask a Question