Candidats naturels pour la hiérarchie au sein de NPI

Supposons que . N P I est la classe de problèmes en N P qui ne sont ni en P ni en N P -hard. Vous pouvez trouver une liste des problèmes supposés être N P I ici .$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$$\mathsf{NPI}$

Le théorème de Ladner nous dit que si alors il y a une hiérarchie infinie de problèmes N P I , c'est-à-dire qu'il y a N P I problèmes qui sont plus difficiles que d'autres problèmes N P $\mathsf{NP}\neq\mathsf{P}$$\mathsf{NPI}$$\mathsf{NPI}$$\mathsf{NPI}$

Je recherche des candidats pour de tels problèmes, c'est-à-dire que je suis intéressé par des paires de problèmes
- , - A et B sont supposés être N P I , - A est connu pour se réduire à B , - mais il y a aucune réduction connue de B à A .$A,B \in \mathsf{NP}$
$A$$B$$\mathsf{NPI}$
$A$$B$
$B$$A$

Encore mieux s'il existe des arguments pour les soutenir, par exemple, il y a des résultats que ne réduit pas à A en supposant certaines conjectures en théorie de la complexité ou en cryptographie.$B$$A$

Existe-t-il des exemples naturels de tels problèmes?

Exemple: Le problème d'isomorphisme graphique et le problème de factorisation d'entier sont conjecturés pour être dans et il existe un argument soutenant ces conjectures. Y a-t-il des problèmes de décision plus difficiles que ces deux-là mais pas connus pour être N P- dur?$\mathsf{NPI}$$\mathsf{NP}$

Groupe Isomorphisme Graphique Isomorphisme ≤ m Anneau Isomorphisme. Factorisation entière ≤ m Isomorphisme en anneau [ Kayal et Saxena ]. Aussi Automorphisme graphique ≤ m Isomorphisme graphique.$\leq_m$$\leq_m$$\leq_m$$\leq_m$

Non seulement il n'y a pas de réductions connues dans l'autre sens, mais il n'y a pas de réduction du graphique Iso au groupe Iso [ Chattopadhyay, Toran et Wagner ].$\mathsf{AC}^0$

Notez qu'une réduction de l'isomorphisme en anneau à l'isomorphisme graphique fournirait également une réduction de la factorisation entière à l'isomorphisme graphique. Pour moi, une telle réduction serait surprenante mais peut-être pas choquante.

(Pour Graph Automorphism vs Graph Isomorphism, leurs versions de comptage sont connues pour être équivalentes les unes aux autres et équivalentes à la décision de Graph Isomorphism. Cependant, cela ne veut pas nécessairement dire grand-chose, car la version de comptage de la correspondance bipartite est équivalente à la version de comptage de SAT. )

Je ne pense pas qu'il y ait un véritable consensus sur ce point , le cas échéant, de ceux - ci sont en fait dans . Si l'un de ces problèmes est N P- complet, alors P H s'effondre au deuxième niveau. Si l' affacturage est N P -complete, il se réduit au premier niveau, soit N P = c o N P .$\mathsf{P}$$\mathsf{NP}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{NP} = \mathsf{coNP}$

De plus, il me semble que l'utilisation de techniques similaires à Ladner peut montrer que tout ordre partiel dénombrable peut être intégré dans l'ordre sur les problèmes de N P (il ne s'agit donc pas seulement d'une hiérarchie, mais d'un ordre partiel dénombrable arbitrairement compliqué) .$\leq_{m}$$\mathsf{NP}$