Théorie de la complexité Conséquences de $\mathsf{NP} = \mathsf{QP}$

Question

J'ai un certain résultat d'impossibilité qui tient à moins que $\mathsf{NP} = \mathsf{QP}$. Il semble fort probable que l'on puisse renforcer cela pour tenir à moins que$\mathsf{NP} = \mathsf{P}$, que je n'aurais pas besoin de motiver davantage dans mon article.

Malheureusement, je n'ai pas le temps de faire cela dans cet article en particulier, alors je veux plutôt motiver rapidement les cryptographes pourquoi $\mathsf{NP} = \mathsf{QP}$est peu probable. Je connais les conséquences de base (à savoir que cela violerait gravement pratiquement toute forme d'ETH, ce qui impliquerait donc que le jeu dominant le tournoi est en P ), mais pas grand chose d'autre.

Bien sûr, il y a aussi la motivation évidente $\mathsf{NP} = \mathsf{QP}$ implique $\mathsf{NP}\cap\mathsf{coNP}\subseteq \mathsf{QP}$. La plupart des hypothèses de dureté utilisées dans la cryptographie sont en$\mathsf{NP}\cap\mathsf{coNP}$, et une hypothèse de dureté faible particulière (log discret de champ fini caractéristique fixe) est connue pour $\mathsf{QP}$. On peut donc interpréter$\mathsf{NP} = \mathsf{QP}$ car "la plupart des hypothèses de dureté en crypto sont à peu près comparables à un log discret à champ fini caractéristique fixe", ce qui peut bien fonctionner comme motivation.

Pourtant, y a-t-il une motivation plus claire du point de vue de la théorie de la complexité? Par exemple, un effondrement de la hiérarchie / quelque chose du genre.

Answer 1

Nous pouvons prouver $\mathrm{NP\ne QP}$ inconditionnellement: $\mathrm{QP}$ est fermé sous des réductions de temps quasipolynomiales, alors que $\mathrm{NP}$ n'est pas (un simple argument de remplissage montre que la fermeture de $\mathrm{NP}$ sous les réductions de temps quasipolynomial inclut tous les langages calculables en temps quasipolynomial non déterministe, et cette classe contient strictement $\mathrm{NP}$ par le théorème non déterministe de la hiérarchie temporelle).

Quant aux conséquences de l'hypothèse la plus faible $\mathrm{NP\subseteq QP}$, voir la question Is NP in$DTIME(n^{poly\log n})$? .