¿ es "mínimo", es decir, implica

Supongamos que $\Pi$ es un problema de decisión decidible.

¿ $\Pi\not \in NP$ implica $\Pi$ is $NP$ -Hard?

Editar: si suponemos que existe $\Pi\in coNP\setminus NP$ entonces hemos terminado. ¿Podemos refutar el reclamo sin suposiciones desconocidas?

Si supone que , cualquier problema de coNP completo da un contraejemplo. Supongo que uno puede refutar su conjetura incondicionalmente.$\mathsf{NP}\neq\mathsf{coNP}$

Si entonces$P=NP$

$\Pi \not\in NP$
$\implies$
$P=NP$ y no es el idioma vacío ni el idioma completo es duro.$\Pi$
$\implies$
$\Pi$$NP$

Supongamos que denota el resultado de poner un 1 inicial en el extremo más significativo de luego analizar el resultado como un entero en binario.$\operatorname{int}(s)$$s$

Si entonces para cada subconjunto de que no está en , no está en NP ya que es demasiado difícil, es decidible si y solo si es, y no es NP-duro, incluso con respecto a las reducciones de Turing ya que para cualquier enlace polinómico, solo existen muchas posibilidades polinomiales para el subconjunto de ese lenguaje que consiste en los elementos que se ajustan dentro del límite de longitud, por lo que uno podría probar reducción de búsqueda a decisión con cada uno de ellos.$P\neq NP$ $S$$\{0,1\}^*$$\operatorname{NTIME}$$\left(2^{O\left(2^n\right)}\right)$
$\{111 \ldots [2^{\operatorname{int}(n)} \text{ of them}] \ldots 111 : n\in S\}$$S$$S$

La integridad de una clase significa que es universal para la clase, es decir, otros problemas en la clase se pueden resolver con ella. Si hay un problema difícil en una clase, todos los problemas universales para la clase también serán difíciles. Pero lo contrario no es válido: la dificultad no implica universalidad. Por ejemplo, el hecho de que un problema no pueda resolverse en un tiempo polinomial no determinista no implica que sea NP completo (es decir, universal para NP).

Para NP: si P = NP, todos los problemas, excepto los triviales, se completarán para NP (bajo las reducciones de Karp). Por lo tanto, suponga que P es un subconjunto adecuado de NP (o, alternativamente, use una noción de reducción más débil como AC0).

Considere un lenguaje unario que está fuera de NP. (Es un ejercicio fácil demostrar que hay idiomas unarios de dificultad arbitraria). El lenguaje no puede ser completo para NP por el teorema de Mahoney.