Est

Supposer $\Pi$ est un problème de décision décidable.

Est-ce que $\Pi\not \in NP$ impliquer $\Pi$ est $NP$-Difficile?

Edit: si l'on suppose qu'il existe $\Pi\in coNP\setminus NP$alors nous avons terminé. Pouvons-nous réfuter la réclamation sans hypothèses inconnues?

Si vous supposez que $\mathsf{NP}\neq\mathsf{coNP}$alors tout problème coNP-complet donne un contre-exemple. Je suppose que l'on peut réfuter sans condition votre conjecture.

Si $P=NP$ puis

$\Pi \not\in NP$
$\implies$
$P=NP$ et $\Pi$ n'est ni la langue vide ni la langue complète
$\implies$
$\Pi$ est $NP$-difficile.

Laisser $\operatorname{int}(s)$ dénoter le résultat de mettre un 1 en tête à l'extrémité la plus significative de $s$ puis en analysant le résultat comme un entier en binaire.

Si $P\neq NP$puis pour chaque sous-ensemble $S$ de $\{0,1\}^*$ ce n'est pas dans $\operatorname{NTIME}$$\left(2^{O\left(2^n\right)}\right)$,
$\{111 \ldots [2^{\operatorname{int}(n)} \text{ of them}] \ldots 111 : n\in S\}$ n'est pas en NP depuis $S$ est trop difficile, est décidable si et seulement si $S$est, et n'est pas NP-difficile même en ce qui concerne les réductions de Turing, car pour toute limite polynomiale, il n'y a que de nombreuses possibilités polynomiales pour le sous-ensemble de ce langage composé des éléments qui s'inscrivent dans la limite de longueur, donc on pourrait essayer la recherche- réduction à la décision avec chacun d'eux.

L'exhaustivité d'une classe signifie qu'elle est universelle pour la classe, c'est-à-dire que d'autres problèmes dans la classe peuvent être résolus en l'utilisant. S'il y a un problème difficile dans une classe, tous les problèmes universels pour la classe seront également difficiles. Mais l'inverse ne tient pas: la difficulté n'implique pas l'universalité. Par exemple, le fait qu'un problème ne peut pas être résolu en temps polynomial non déterministe n'implique pas qu'il est NP-complet (c'est-à-dire universel pour NP).

Pour NP: si P = NP, tous les problèmes, sauf les plus triviaux, seront complets pour NP (sous les réductions de Karp). Supposons donc que P est un sous-ensemble approprié de NP (ou utilisez une notion de réduction plus faible comme AC0).

Considérons une langue unaire qui est en dehors de NP. (C'est un exercice facile de montrer qu'il existe des langues unaires de difficulté arbitraire.) La langue ne peut pas être complète pour NP par le théorème de Mahoney.