In ihrer Arbeit (S. 503) bemerken Garey und Johnson:
... es könnte ein NP-vollständiges Problem geben, das weder im engeren Sinne NP-vollständig noch durch einen pseudo-polynomiellen Zeitalgorithmus lösbar ist ...
Kennt jemand einige Kandidatenprobleme mit den oben genannten Eigenschaften?
Ich denke, die mögliche Antwort auf diese Frage kann eine Liste von NP-vollständigen Problemen im gewöhnlichen Sinne sein, so dass für sie kein pseudopolynomieller Algorithmus bekannt ist.
ds.algorithms
np-hardness
np
Oleksandr Bondarenko
quelle
quelle
Antworten:
Ich weiß nicht, ob Sie mehr über meinen Kommentar zu Ihrer Frage erfahren möchten, aber hier finden Sie trotzdem mehr Details.
Wenn P = NP, kann jedes Problem in NP in Polynomzeit und damit in Pseudo-Polynomzeit gelöst werden, was bedeutet, dass kein Problem Ihre Anforderung erfüllt, wie Magnus in seiner Antwort bemerkte. Nehmen wir also im Rest dieser Antwort P ≠ NP an.
Wegen P ≠ NP existiert eine Sprache L ∈NP ∖ P, die nicht NP-vollständig ist (Ladner-Theorem). Betrachten Sie das folgende Problem:
Direktes Produkt von Partition und L-
Instanz : m positive ganze Zahlen a 1 ,…, a m und k ganze Zahlen b 1 ,…, b k ∈ {0,1}.
Frage : Haben beide der folgenden Aussagen Gültigkeit?
(1) Die m ganzen Zahlen a 1 ,…, a m bilden eine Ja-Instanz des Partitionsproblems.
(2) Die k -Bit - String b 1 ... b k gehört L .
Definieren Sie nach dem Artikel von Garey und Johnson die Längenfunktion als m + mlog max i a i ⌉ + k und die Max-Funktion als max i a i .
Es ist eine Routine, um zu überprüfen, (i) ob es im schwachen Sinne NP-vollständig ist, (ii) ob es keinen Pseudo-Polynom-Zeit-Algorithmus gibt und (iii) ob es im starken Sinne NP-vollständig ist Sinn.
(Hinweise: (i) Die Zugehörigkeit zu NP ergibt sich aus der Tatsache, dass sowohl das Partitionsproblem als auch L in NP sind. Reduzieren Sie Partition für NP-Härte auf dieses Problem. (Ii) Konstruieren Sie eine pseudo-polynomiale Transformation von L zu diesem Problem. (iii) Konstruieren Sie eine Pseudo-Polynom-Transformation von diesem Problem nach L, indem Sie die Tatsache verwenden, dass Partition einen Pseudo-Polynom-Zeit-Algorithmus hat.)
Das Partitionsproblem in dieser Konstruktion hat nichts Besonderes: Sie können Ihr bevorzugtes, schwach NP-vollständiges Problem mit einem Pseudo-Polynom-Zeit-Algorithmus verwenden.
quelle
Ich würde sagen, die Antwort ist eindeutig nein (das heißt, niemand weiß es), weil niemand weiß, ob die NP-vollständigen Probleme in Polynomzeit gelöst werden können, geschweige denn in Pseudo- Polynomzeit. (Jeder Polynomalgorithmus ist natürlich pseudopolynom.) Wenn Sie in NPC ein Problem finden, das in pseudopolynomialer Zeit nicht gelöst werden kann, haben Sie gerade bewiesen, dass P ≠ NP ist jederzeit bald produziert.
quelle