Das Partitionsproblem ist schwach NP-vollständig, da es einen Polynom-Zeitalgorithmus (Pseudo-Polynom-Zeitalgorithmus) aufweist, wenn die Eingabe-Ganzzahlen durch ein Polynom begrenzt sind. 3-Partition ist jedoch ein starkes NP-vollständiges Problem, selbst wenn die Eingabe-Ganzzahlen durch ein Polynom begrenzt sind.
Unter der Annahme, , können wir beweisen, dass intermediäre NP-vollständige Probleme existieren müssen? Wenn die Antwort ja ist, gibt es ein solches "natürliches" Kandidatenproblem?
Das Intermediate NP-complete-Problem ist hier ein Problem, das weder einen pseudo-polynomialen Zeitalgorithmus noch NP-complete im engeren Sinne aufweist.
Ich vermute, dass es eine unendliche Hierarchie von NP-vollständigen Zwischenproblemen zwischen schwacher NP-Vollständigkeit und starker NP-Vollständigkeit gibt.
EDIT 6. März : Wie in den Kommentaren erwähnt, ist eine alternative Möglichkeit, die Frage zu stellen:
Angenommen, , können wir die Existenz von NP-vollständigen Problemen beweisen, die weder einen polynomiellen Zeitalgorithmus noch NP-vollständige haben, wenn die numerischen Eingaben in Unärzahl dargestellt werden? Wenn die Antwort ja ist, gibt es ein solches "natürliches" Kandidatenproblem?
EDIT2 6. März : Die umgekehrte Richtung der Implikation ist wahr. Die Existenz solcher "intermediärer" -kompletter Probleme impliziert P ≠ N P, da bei P = N P unäre N P -komplette Probleme in P sind .
quelle
Antworten:
Dies ist eine Teilantwort, die nur ein Kandidaten-Zwischen- -vollständiges Problem ergibt.NP
-Equal Sum Subsets Problem: eine Multimenge von Gegeben n positiven ganzen Zahlen A = { a 1 , . . . , a n } gibt es k nicht leere disjunkte Teilmengenk n A={a1,...,an} k so, dass s u m ( S 1 ) = . . .S1,...,Sk⊆{a1,...,an} ?sum(S1)=...=sum(Sk)
Das Problem ist schwach -vollständig, wenn k = O ( 1 ) und hat daher einen pseudo-polynomialen Zeitalgorithmus für jede feste konstante ganze Zahl k > 2 . Es wird jedoch stark N P -komplette wenn die Anzahl der Untergruppen gleich Summe k = Ω ( n ) .NP k=O(1) k>2 NP k=Ω(n)
Wenn und k = O ( log n ) ist, dann ist das k -Equal Sum Subsets-Problem ein Kandidaten-Zwischen- N P -Vollständigkeitsproblem (wie in der Frage beschrieben). Es ist weder bekannt, dass dieses Problem einen pseudo-polynomialen Zeitalgorithmus aufweist, noch dass es im starken Sinne N P -vollständig ist.k=ω(1) k=O(logn) k NP NP
Referenz:
CIELIEBAK, EIDENBENZ, PAGOURTZIS und SCHLUDE über die Komplexität von Variationen gleicher Summenteilmengen, Nordic Journal of Computing 14 (2008), 151–172
quelle