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

22

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 .PNPNPichNPPNPNPich

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.NPPNPichNPichNPich

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 .EIN,BNP
EINBNPich
EINB
BEIN

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 .BEIN

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?NPichNP

Mohammad Al-Turkistany
quelle
1
Sie suchen also nach Problemen so dass P 1 p P p P 2 mit P 1N P I und P 2N P C ist ? PNPP1pPpP2P1NPichP2NPC
Raphael
1
Ja, aber es ist keine Reduktion von P nach P1 bekannt (ähnlich keine bekannte Reduktion von P2 nach P).
Mohammad Al-Turkistany
2
Es gibt mehrere Probleme mit einem faktorähnlichen
Marcos Villagra
8
Außerdem haben wir eine sehr schöne Liste in cstheory cstheory.stackexchange.com/questions/79/…
Marcos Villagra
2
Warum ist die Liste, auf die Marcos verweist, nicht die Antwort auf Ihre Frage?
Suresh

Antworten:

5

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 !nxy . 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!mody

Marcos Villagra
quelle
1
Ich glaube, das OP sucht nach Problemen in NP. Können Sie dies als Entscheidungsproblem umformulieren?
Zach Langley
FNP ist die Funktionsversion (dh Suchprobleme) von NP. In der Tat ist Factoring nicht in NP, es ist FNP. Zum Beispiel ist das Entscheidungsproblem beim Factoring trivial, die Komplexität ist nur 0 (1), aber das Suchproblem ist der schwierige Teil. Da das OP Factoring als Beispiel angeführt hat, halte ich dies auch für eine gültige Antwort.
Marcos Villagra
1
nknd1<dk
@ Marcos, Danke. Ich interessiere mich für Entscheidungsprobleme in NP.
Mohammad Al-Turkistany
x!modyk