NP-vollständige Probleme und die "3".

[MrN_zu_faul_zum_Login]

Ich denke es liegt daran, dass je näher an 0 eine (ganze) Zahl ist, desto wichtiger ist sie in diversesten Problemen. Und 3 ist eine sehr kleine Zahl, deswegen ist es unvermeidbar dass sie oft vorkommt.

[berniebutt]

Also andere Beispiele:

--> Die drei von der Tankstelle (uralter Film)
--> Die drei Musketiere
--> Der Hocker mit drei Beinen steht besser als der mit vier Beinen
--> Die Männer vom Sägewerk mit noch drei Fingern
--> Das Dreigestirn im Kölner Karneval

Scheint doch sehr bedeutsam zu sein die Zahl drei!

[SideWinder]

Bei vielen Problemen gibt es für Fälle <=2 eben noch mögliche Vereinfachungen die erst auf die Verallgemeinerung in die 3. Dimension verloren gehen.

MfG SideWinder

[Gregor]

Ich hatte eigentlich bewusst Interpretationsspielraum in der Frage gelassen, da ich mir selbst nicht über die beste Formulierung im Klaren bin und ich auch an weit hergeholten Ideen interessiert bin. Teilweise gehen die Antworten hier aber aus meiner Sicht etwas zu weit in den Offtopic Bereich, deshalb konkretisiere die Frage mal:

Bei dem Erfüllbarkeitsproblem der Aussagenlogik sieht man, dass es bezüglich der Komplexität einen fundamentalen Unterschied macht, ob man 3 oder 2 Literale pro Klausel hat. Während 2-SAT effizient lösbar ist, ist 3-SAT NP-vollständig. Andererseits ist 582-SAT nicht fundamental schwerer zu lösen als 3-SAT. Es scheint hier also eine sehr prinzipielle Schwelle in der Problemstruktur überschritten zu werden, wenn man von 2 auf 3 Literale pro Klausel geht.

Ähnliches kann man auch beim Färbungsproblem von Graphen sehen. Während es effizient entscheidbar ist, ob ein Graph 2-färbbar ist, ist 3-Färbbarkeit wiederum NP-vollständig.

Was macht bei diesen Beispielen die Komplexität der 3er-Varianten gegenüber den 2er-Varianten aus? Letztendlich müssen die jeweiligen Probleme dann ja in ihrer Struktur wesentlich komplexer sein. Lässt sich das, was diese erhöhte Komplexität ausmacht, in Worte fassen und auf andere NP-vollständige Probleme übertragen? Und: Es gibt auch andere NP-vollständige Probleme, die in einschränkenden Formulierungen effizient gelöst werden können. Entsteht auch hier das schwer lösbare Problem, wenn solche "3er-Abhängigkeiten" im Problem auftauchen?

[Gregor]

SideWinder schrieb:

Bei vielen Problemen gibt es für Fälle <=2 eben noch mögliche Vereinfachungen die erst auf die Verallgemeinerung in die 3. Dimension verloren gehen.

Ich finde es interessant, dass Du hier von Dimensionen redest. Ist das bewusst? Kann man da etwas als Dimension sehen?

[Jester]

Ich glaube ein wichtiger Grund ist, dass sich mit Tripeln in vielen Fällen auch k-tupel formulieren lassen, was bei 2-tupeln oft noch nicht möglich ist.

Bei der 2-Färbbarkeit ist es so, dass stark ausgenutzt wird, dass halt nurnzwei Farben verwendet werden. Wenn man nun weiß, dass (bei farben rot und grün) ein Knoten nicht rot ist, dann muss er halt grün sein und umgekehrt. Bei drei Farben weiß man bei "nicht rot" eben auch nur genau das.

[SideWinder]

@Gregor: Nein, ich habe den Begriff unwissend gewählt. Jesters Erklärung finde ich besser. Solange -A -> B und -B -> A gilt hat man es wesentlich einfacher. Unsere Bool'sche Logik hat dementsprechend nur die zwei Dimensionen Wahr/Falsch oder so

MfG SideWinder

[Jester]

3SAT benutzt aber auch nur zwei wahrheitswerte. Allerdings kann man da eben sowas dreiwertiges ausdrücken a oder b oder c lässt sich ja schreiben als "nicht a => b oder c", also ganz ähnlich wie bei mehr als zwei farben zur auswahl.

[hustbaer]

Ich hätte noch das Dreikörperproblem anzubieten.
Das ist gleich gar nicht mehr genau lösbar, wohingegen die Lösung mit 2 Körpern noch recht einfach ist.

[Michael E.]

Bipartite Matchings sind einfach, aber dreidimensionale Matchings sind NP-vollständig.

[Sone]

3x+1, an dem habe ich Stunden über Stunden gesessen.

2x+1 hingegen macht keinen Sinn, wobei x+1 natürlich eine völlig triviale Lösung hat.