Natürliche Kandidaten für die Hierarchie innerhalb des NPI

Nehmen wir an , dass . N P I ist die Klasse von Problemen in N P, die weder in P noch in N P -hard sind. Eine Liste der Probleme, von denen vermutet wird, dass sie N P I sind, finden Sie hier .$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$$\mathsf{NPI}$

Das Ladner-Theorem besagt, dass es, wenn ist, eine unendliche Hierarchie von N P I -Problemen gibt, dh, es gibt N P I -Probleme, die schwerer sind als andere N P I -Probleme.$\mathsf{NP}\neq\mathsf{P}$$\mathsf{NPI}$$\mathsf{NPI}$$\mathsf{NPI}$

Ich bin auf der Suche nach Kandidaten für solche Probleme, dh ich interessiere mich für Problempaare
- , - A und B werden als N P vermutet. I , - A reduziert sich bekanntermaßen auf B , - gibt es aber Keine Reduktionen von B nach A bekannt .$A,B \in \mathsf{NP}$
$A$$B$$\mathsf{NPI}$
$A$$B$
$B$$A$

Noch besser, wenn es Argumente dafür gibt, z. B. gibt es Ergebnisse, die der Annahme einiger Vermutungen in der Komplexitätstheorie oder Kryptographie nicht auf A reduziert .$B$$A$

Gibt es natürliche Beispiele für solche Probleme?

Beispiel: Es wird vermutet, dass das Graph-Isomorphismus-Problem und das Integer-Faktorisierungs-Problem in und es gibt Argumente, die diese Vermutungen stützen. Gibt es Entscheidungsprobleme, die schwerer sind als diese beiden, von denen jedoch nicht bekannt ist, dass sie N P -hart sind?$\mathsf{NPI}$$\mathsf{NP}$

Ich habe ein nettes Problem mit dem Namen ModularFactorial gefunden . Nehmen Sie als Eingabe zwei stellige Ganzzahlen x und y und geben Sie x aus $n$$x$$y$ . Dieses Problem ist mindestens so schwer wieFactoringund es ist nicht bekannt, dass es fürFNPschwierig ist. Die Referenz ist das jüngste (und schönste) Buch von Cristopher Moore und Stephan MertensThe Nature of Computation, Seite 79.$x! \mod y$