Kann es in NP-Complete ein endliches Problem geben?

Mein Dozent gab die Erklärung ab

Jedes endliche Problem kann nicht NP-vollständig sein

Er sprach zu der Zeit über Sudokus und sagte etwas in der Art, dass es für ein 8x8-Sudoku eine endliche Menge von Lösungen gibt, aber ich kann mich nicht genau erinnern, was er gesagt hat. Ich habe die Notiz aufgeschrieben, die ich zitiert habe, aber immer noch nicht wirklich verstehe.

Sudokus sind NP komplett, wenn ich mich nicht irre. Das Clique-Problem ist auch NP-Complete und wenn ich ein 4-Clique-Problem hätte, ist dies kein endliches Problem, das NP-Complete ist?

np-complete np TheRapture87
quelle

Was ist ein "endliches Problem"? Google und Wikipedia helfen nicht.

Anton Trunov

@AntonTrunov Ein Problem, bei dem die Eingabe die Länge begrenzt hat.

Yuval Filmus

@YuvalFilmus, Gilt das nicht für alle gültigen Turing-Maschinen * -Eingabepaare? IIRC eines der Symbole wird die bezeichnete leere Symbol und der Eingang hat anfänglich einen begrenzten Bereich außerhalb , die andere Symbole als das Leersymbol nicht erscheinen kann. Der Begriff "NP vollständig" wird normalerweise nicht im Kontext von Operationen auf Streams verwendet, die nicht modelliert werden können, ohne diese Annahme zu lockern.

Mike Samuel

@ MikeSamuel Wenn ich begrenzte Länge sage, meine ich die Eingabe von höchstens 100. (oder einer anderen Zahl als 100.)

Yuval Filmus

@YuvalFilmus, ok. Ich sage, der Begriff "NP vollständig" wird nur verwendet, wenn keine nicht leeren Symbole in der Eingabe vorhanden sind oder wenn eine Ganzzahl vorhanden ist, die die Anzahl der Symbole zwischen dem ganz linken nicht leeren Symbol und dem ganz rechten nicht leeren Symbol darstellt . 100 wäre ein solches Beispiel.

Mike Samuel

Antworten:

Wenn ein endliches Problem NP-vollständig ist, dann ist P = NP, da jedes endliche Problem einen polynomiellen Zeitalgorithmus (sogar einen konstanten Zeitalgorithmus) hat.

Wenn wir sagen, dass Sudoku NP-vollständig ist, meinen wir, dass eine verallgemeinerte Version von Sudoku, die auf einem Brett gespielt wird, NP-vollständig ist. $n^2 \times n^2$

Schließlich ist das 4-Clique-Problem, obwohl es kein endliches Problem ist (der Eingabediagramm hat eine unbegrenzte Größe), ein einfaches Problem, das einen polynomiellen Zeitalgorithmus aufweist.

Yuval Filmus
quelle

Ist das 4-Cliquen-Problem P also ein polynomieller Zeitalgorithmus?

TheRapture87

@ Aceboy1993 Richtig, das ist die Definition von P.

Yuval Filmus

Aber warum wird K-Clique dann als NP-Complete eingestuft? Stellt K nicht nur eine Zahl wie 4 dar?

TheRapture87

@ Aceboy1993 Nein, ist Teil der Eingabe. Für konstante das Problem in P.

k

$k$

k

$k$

Yuval Filmus

Wir können auch beweisen, dass Clique NP-vollständig ist.

Yuval Filmus

Die Aussage Ihres Lehrers ist falsch oder Sie haben ihn wahrscheinlich nicht richtig verstanden. Die richtige Aussage ist

Beliebige endliche Sprache mit kann nur NP-vollständig sein, wenn . $L$ $|L| \geq 1$ $P = NP$

Das liegt daran, dass wir (wie im Jahr 2016) immer noch nicht wissen, ob . Auch ist wichtig, weil (die leere Sprache) niemals NP-vollständig sein kann, egal ob oder . $P \neq NP$ $|L|>1$ $\emptyset$ $P=NP$ $P \neq NP$

Sudoku oder Schach sind nicht NP-vollständig (wie Yuval hervorgehoben hat), weil ihre Eingabe eine Größe von 9x9 oder 8x8 hat (ich spreche über die Entscheidungsversionen, ob Sudoku eine Lösung hat oder ob Schach eine Gewinnstrategie hat). Beim Schach gehe ich davon aus, dass eine wiederholte Position als Unentschieden gewertet wird.

Shreesh
quelle

Rückruf: Ein Problem X ist NP-vollständig, wenn es zwei Kriterien erfüllt:

a) Es ist in NP - dh jede erratene Lösung von X kann in Polynomzeit verifiziert werden.

b) Es ist vollständig für NP - Dh jedes Problem Y in NP hat eine Polynomzeitreduktion, die eine Instanz von Y in eine Instanz von X übersetzt (so dass jedes Polynomzeitprogramm, das X löst, auch Y in Polynomzeit löst ).

Wir können uns darauf einigen, dass ein 9x9 Sudoku (a) erfüllt. Es ist (b), wo die Dinge herunterfallen. Allgemeiner - Probleme (in NP oder anders) haben typischerweise Instanzen der Größe N für willkürlich große Werte von N ; Dies gilt sicherlich für die bekannten Probleme in NP. Eine Reduzierung von einem solchen Problem auf ein Problem mit einer maximal möglichen Problemgröße kann unmöglich eine gültige Reduzierung von Instanz zu Instanz sein, da erstere immer (unendlich) mehr Instanzen als letztere hat. Aus diesem Grund muss Sudoku auf NxN-Matrizen verallgemeinert werden, bevor die NP-Vollständigkeit berücksichtigt werden kann.

PMar
quelle

Das ist nicht richtig. Es ist durchaus möglich, eine gültige Reduktion von einem Problem mit unendlich vielen Instanzen auf ein Problem mit endlich vielen Instanzen zu haben. Hier ist zum Beispiel eine Reduktion von SAT auf das Problem der Bestimmung, ob eine Zeichenfolge der Länge 1 gleich "a" ist: Wenn die SAT-Instanz erfüllbar ist, ordnen Sie sie der Zeichenfolge "a" zu; Andernfalls ordnen Sie es der Zeichenfolge "b" zu. Nun, diese Reduktion ist (wahrscheinlich) nicht in Polynomzeit berechenbar, aber es ist eine vollkommen gültige Reduktion.

David Richerby