Kann eine Teilmenge eines NP-vollständigen Problems in P sein?

7

Das Problem ist NP-vollständig (bewährt) für alle Eingabedaten (ohne Ausnahme).

Wir nehmen an, dass P! = NP.

Ist es möglich, dass es eine (unendlich große) Teilmenge des Problems gibt, für die sich diese Teilmenge in P befindet?

Theoretische Frage.

Aurelio
quelle
15
Es gibt kein "NP-vollständig für alle Eingabedaten". Wenn die Eingabe fest ist, ist auch die Laufzeit festgelegt.
John Dvorak
Die Eingabe hat keine feste Größe. Die Eingabe wächst linear und die Ausführungszeit nimmt exponentiell zu (NP-vollständig für dieses Problem X ist bewiesen).
Aurelio
9
Bitte senden Sie nicht dieselbe Frage an mehrere Stack Exchange-Sites. Dies verstößt gegen die Richtlinien der Website, da Antworten fragmentiert werden und die Zeit verschwendet wird, die Benutzer für die Beantwortung von Fragen aufwenden, die an anderer Stelle beantwortet wurden.
David Richerby
Wenn ich meine Vorstellungen im folgenden Beispiel richtig habe und die Absicht Ihrer Frage richtig interpretiere, können Sie ZUFRIEDENHEIT vs. 2-SAT in Betracht ziehen. Ersteres ist in NP-Complete, während letzteres in P ist. Sie können dies sogar auf NP-Härte ausdehnen: eine Lösung mit minimaler Unterstützung findenAx=b ist im Allgemeinen NP-schwer, wird aber ziemlich schnell erledigt, wenn Sie einschränken Aein Element des Satzes invertierbarer Matrizen zu sein (die Lösung mit minimalem Gewicht wäre die einzigartige Lösung).
Thomas Rasberry
Ich denke, die wichtigste Erkenntnis hier, warum die Frage keinen Sinn ergibt, sind nicht die Grenzen der Eingabegröße, sondern die Tatsache, dass die NP-Vollständigkeit behauptet, dass für alle Eingaben des Problems, die reduziert werden , eine Reduzierung Ihres Problems besteht (mit eine entsprechende Eingabe). Es ist nicht universell quantifiziert über den Input des Problems, auf das reduziert wird.
22.

Antworten:

23

Ihre Frage macht keinen Sinn:

Das Problem ist NP-vollständig (bewährt) für alle Eingabedaten (ohne Ausnahme).

Das ist keine Sache. Die NP-Vollständigkeit ist eine Eigenschaft ganzer Mengen, nicht spezifischer Eingaben. Es ist ziemlich trivial zu zeigen, dass jedes Problem besteht , wenn Sie eine bestimmte Eingabe auswählenO(1)zu diesem Eingang: Sie geben nur Ja oder Nein aus, je nachdem, was für Ihren Eingang richtig ist. Wenn Sie dies tun, bricht die gesamte Algorithmusanalyse zusammen und alles wird unbrauchbar. Also machen wir das nicht.

P, NP, NP- Vollständigkeit, Polynomzeit usw. hängen alle mit der asymptotischen Komplexität zusammen : Wie wächst die Laufzeit, wenn die Größe der Eingabe zunimmt ? Dies ist nur dann sinnvoll, wenn Sie verschiedene Eingaben betrachten. Ebenso ist die Ableitung eines Punkts im Kalkül eine Eigenschaft, die die den Punkt umgebende Kurve berücksichtigt.

Wir nehmen an, dass P! = NP.

Auch dies hat keinen Einfluss auf Ihre Antwort. WennP=NPdann jeder P gesetzt ist NP-complete, * also gibt es eine Reihe von Teilmengen inP. Und wennP=NPDie Beispiele, die Menschen gegeben haben, sind alle gültig.

Ist es möglich, dass es eine Teilmenge des Problems gibt (unendlich groß), dass dieses Problem in P ist?

Ja, und die anderen Antworten haben gute Beispiele dafür gegeben. Aber für die Nachwelt ist hier noch ein weiteres Gegenbeispiel.

  • k-Farbe ist NP-Vollständig, wenn Sie nehmen k als Eingabe, aber 2-Farbe ist eine unendliche Teilmenge davon, die in ist P.

* Ausser für und Σ, die nicht sind NP-Komplett aus technischen Gründen in Bezug auf die Form der Ermäßigungen, die wir zur Definition der Vollständigkeit verwenden.

jmite
quelle
Danke @DavidRicherby für die Klarstellung am und Σ
Jmite
13

Tatsächlich brauchen Sie das P nichtNP- Hypothese, da es sogar unendlich viele zeitlich konstituierbare Teilmengen von NP- vollständigen Problemen gibt. Für jede NP- vollständige SpracheL{0,1}, Lassen L={0wwL}{1ww{0,1}}. L ist immer noch NP- vollständig (triviale Reduktion von L), enthält jedoch die unendliche, zeitlich konstante, entscheidbare Teilmenge aller Zeichenfolgen, die mit beginnen 1.

David Richerby
quelle
10

Soweit ich Ihre Frage verstehe, ist dies möglich. Betrachten Sie als Beispiel die (unendlich große) Teilmenge von SAT, die alle erfüllbaren Formeln ohne Negationen enthält. Diese Untergruppe ist trivial in P.

Pontus
quelle
Falsch verstanden. SAT ist nur ein Beispiel. Ich schrieb, dass für alle Fälle NP-vollständig ist. Die SAT-Klasse P ist, wenn sie die Bedingungen des Dichotomie-Theorems von Schaefer erfüllt ( en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem ). Es gibt eine von Ihnen erwähnte Bedingung. Was aber, wenn sich herausstellt, dass es eine Teilmenge der Klasse P gibt und nicht (diese Teilmenge) zum Dichotomiesatz von Schaefer gehört?
Aurelio
Jetzt habe ich keine Ahnung, was Sie fragen. Ich denke, Sie müssen Ihre ursprüngliche Frage bearbeiten und klären.
Pontus
7
@Aurelio Die Klasse der negationsfreien Formeln ist genau das, wonach Sie gefragt haben: ein unendliches polynomialzeitentscheidbares Teilproblem eines NP-vollständigen Problems. Wenn Sie nach etwas anderem suchen, müssen Sie Ihre Frage bearbeiten.
David Richerby
9

Nehmen Sie das Beispiel von 3-Coloring Problem ist es NP-Complete im Allgemeinen, aber für Bäume (es gibt unendlich viele) ist es in P

Shiv
quelle
1

Graph Färbung, maximale Clique und maximale unabhängige Menge sind NP-vollständig (Entscheidungsversionen), aber Polynom auf perfekten Graphen.

Eugene
quelle
0

Nehmen Sie das Problem des Handlungsreisenden: Gegeben sind n Städte und die Entfernungen zwischen jedem Städtepaar sowie eine Grenze d. Gibt es eine Route, die jede Stadt einmal berührt und dann mit einer Gesamtlänge ≤ d zum Startpunkt zurückkehrt?

Für jeden Satz von Städten und Entfernungen ist es für kleine Werte von d ("klein" abhängig von den Entfernungen) leicht zu zeigen, dass es keine Lösung gibt, und für große Werte von d ist es einfach, eine Lösung zu finden. Sie können also eine Teilmenge des Problems finden, bei der d groß oder klein genug ist, um jede Instanz in Polynomzeit zu lösen.

gnasher729
quelle