Techniques pour montrer que le problème est dans la dureté

Étant donné un nouveau problème dans dont la véritable complexité se situe quelque part entre et NP-complete, il existe deux méthodes que je connais qui pourraient être utilisées pour prouver que la résolution de ce problème est difficile:$\mathsf{NP}$$\mathsf{P}$

1. Montrer que le problème est GI-complet (GI = Graph Isomorphism)
2. Montrer que le problème est dans $\mathsf{co-AM}$ . Selon les résultats connus, un tel résultat implique que si le problème est NP-complet, alors PH s'effondrera au deuxième niveau. Par exemple, le fameux protocole pour le nonisomorphisme graphique fait exactement cela.

Existe-t-il d'autres méthodes (peut-être avec différentes «forces de conviction») qui ont été utilisées? Quelle que soit la réponse donnée, il faut un exemple d'utilisation concrète: il y a évidemment plusieurs façons de montrer cela, mais les exemples rendent l'argument plus convaincant.

Montrer que votre problème est en mode CoAM (ou SZK) est en effet l’un des principaux moyens de produire des preuves de "limbo dureté". Mais à part cela, il y en a plusieurs autres:

• Montrez que votre problème est dans NP ∩ coNP. (Exemple: affacturage.)
• Montrez que votre problème peut être résolu en un temps quasiipolynomial. (Exemples: dimension VC, approximation des jeux gratuits.)
• Montrez que votre problème n’est pas plus difficile que d’inverser des fonctions à sens unique ou de résoudre NP en moyenne. (Exemples: beaucoup de problèmes en cryptographie.)
• Montrez que votre problème se réduit à (par exemple) des jeux uniques ou une extension en petit groupe.
• Montrez que votre problème est dans BQP. (Exemple: l'affacturage, bien sûr, cela fait également partie de NP ∩ coNP.)
• Éliminer les grandes classes de réductions de NP-complétude. (Exemple: le problème de minimisation de circuit, étudié par Kabanets et Cai.)

Je suis sûr qu'il y en a d'autres que j'oublie.

D'après le commentaire ci-dessus: si un problème semble assez difficile, mais que vous ne pouvez pas prouver qu'il est NP-complet, une vérification rapide consiste à compter le nombre de chaînes de longueur dans la langue: si l'ensemble est clairsemé, il l'est peu probable d'être NPC, sinon P = NP d'après le théorème de Mahaney ... il est donc préférable d'orienter les efforts pour prouver qu'il est en P :-) :-)$n$

Un exemple est le problème de la partition des nombres en k-box (extrait du blog de Fortnow & Gasarch, source originale: Cyberpuzzles du docteur Ecco ):

{ 1 , . . . , n }  dans au plus k cases de sorte qu'aucune case ne possède  x , y , z  avec  x + y = z $\{ (n,k) \mid \text{ there exists a way to partition }$ $\{1,...,n\} \text{ into at most k boxes so that no box has } x,y,z \text{ with } x+y=z \}$

Voici trois ajouts à la liste de Scott:

• Montrez que votre problème est en peu de points. Cela signifie que le nombre de solutions est limité par un polynôme. (Exemple: problème de péage). Aucun problème NP-complet n'est connu dans peu de P. (impossible à moins de peu P = NP).
• $LOGNP$$NP[log^2n]$
• $2^{n^{\epsilon}}$$NP$$\epsilon \gt 0$$n\ge 0$$2^{n^{\epsilon}}$$n$

$coNP ⊆ NP/poly$