Gute Beispiele für „zwei sind einfach, drei sind schwer“ in den Computerwissenschaften

29

Ich bin kürzlich auf eine Formulierung des Meta-Phänomens gestoßen : " Zwei ist einfach, drei ist schwer " (so formuliert von Federico Poloni), die sich wie folgt beschreiben lässt:

Wenn ein bestimmtes Problem für zwei Entitäten formuliert wird, ist es relativ einfach zu lösen. Ein Algorithmus für eine Drei-Entitäten-Formulierung erhöht jedoch die Schwierigkeit enorm und macht möglicherweise sogar die Lösung nicht durchführbar oder nicht erreichbar.

_{(Ich begrüße Vorschläge, um die Formulierung schöner, prägnanter und genauer zu gestalten.)}

Welche guten Beispiele in verschiedenen Bereichen der Computerwissenschaften (beginnend mit der reinen linearen Algebra und endend mit einer pauschalen Computerphysik) kennen Sie?

linear-algebra computational-physics computational-geometry computational-chemistry Anton Menshov
quelle

2

Der Fluch der Dimensionalität kommt mir in den Sinn.

Paul

4

Grafik 2-Färbung ( einfach ) versus 3-Färbung ( NP-hart ), siehe hier

GoHokies

5

@ GoHokies Bitte keine Antworten als Kommentare posten.

David Richerby

4

Aufgrund des mathematischen Hintergrunds oder des rekursiven Hintergrunds können Sie auf die Funktion TREE stoßen , bei der TREE (2) = 3 und TREE (3) ... ziemlich groß ist. (Da ich mit den Computerwissenschaften nicht vertraut bin, bin ich mir nicht sicher, ob dies wirklich eine Antwort ist, nach der Sie suchen, aber es scheint ähnlich genug, um einen Kommentar zu hinterlassen)

BurnsBA

2

Ein Gegenbeispiel: "Fahren Sie niemals mit zwei Chronometern zur See; nehmen Sie einen oder drei." Trotzdem gibt es so viele gute Beispiele, dass es keine richtige Antwort gibt. Diese Frage sollte Community-Wiki sein.

David Hammen

35

Ein Beispiel, das in vielen Bereichen der Physik auftritt, insbesondere in der klassischen Mechanik und der Quantenphysik, ist das Zweikörperproblem. Das Zweikörperproblem bedeutet hier die Aufgabe, die Dynamik zweier wechselwirkender Teilchen zu berechnen, die beispielsweise durch Gravitations- oder Coulombkräfte zusammenwirken. Die Lösung für dieses Problem kann häufig in geschlossener Form durch eine variable Transformation in Massenschwerpunkt- und Relativkoordinaten gefunden werden.

Sobald Sie jedoch drei Partikel betrachten, existieren im Allgemeinen keine Lösungen in geschlossener Form .

Davidhigh
quelle

3

Nitpick, das wissen Sie sicher, aber Ihre Antwort lautet nicht: Es gibt geschlossene Lösungen für das 3-Körper-Problem, aber nur für einige Sonderfälle

Lama

Guter Trottel, danke, hier fehlt "generell".

Davidhigh

Beachten Sie, dass das 3-Körper-Problem eine ( sehr langsam konvergierende) Serienlösung hat, die Sundman zu Beginn des 20. Jahrhunderts gefunden hat, und dass 1990 eine schwächere Version (die Singularitäten ignoriert, bei denen Körper kollidieren) für das n-Körper-Problem gefunden wurde.

WorldSEnder

27

Ein bekanntes Beispiel ist das Boolesche Erfüllbarkeitsproblem (SAT). 2-SAT ist in der Polynomzeit nicht kompliziert zu lösen, aber 3-SAT ist NP-vollständig.

Federico Poloni
quelle

3

3-SAT kann auf 3-Farben oder umgekehrt

GoHokies

8

@ GoHokies Ich dachte, das gilt für jedes np-vollständige Problem? Oder ist an diesen beiden etwas besonders Bemerkenswertes? Sry, wenn das eine dumme Frage ist, sind meine Kenntnisse auf diesem Gebiet grundlegend. Aber so verstehe ich

Kochsatz

2

@findusl Du hast vollkommen recht. Das Besondere an 3-SAT und 3-Farben ist die 2-gegen-3-Dichotomie des OP.

GoHokies

26

In einer und zwei Dimensionen führen alle Straßen nach Rom, aber nicht in drei Dimensionen.

Insbesondere wenn ein zufälliger Gang (der sich mit gleicher Wahrscheinlichkeit in eine beliebige Richtung bewegt) auf den ganzen Zahlen in einer oder zwei Dimensionen erfolgt, gelangt der zufällige Gang mit der Wahrscheinlichkeit eins (auch bekanntlich mit ziemlicher Sicherheit) schließlich zu einem bestimmten Ziel Punkt ("Rom").

Bei drei oder mehr Dimensionen ist die Wahrscheinlichkeit, "Rom" zu erreichen, geringer als eins. mit abnehmender Wahrscheinlichkeit mit zunehmender Anzahl von Dimensionen.

Wenn Sie beispielsweise eine stochastische (Monte Carlo) Simulation eines zufälligen Spaziergangs ab "Rom" durchführen, der bei der Rückkehr nach Rom anhält, können Sie sicher sein, dass Sie es in einer und zwei Dimensionen wieder zurück nach Rom schaffen und die Simulation stoppen - so einfach. In drei Dimensionen schaffen Sie es vielleicht nie wieder, so schwer.

https://en.wikipedia.org/wiki/Random_walk#Higher_dimensions

Um den zweidimensionalen Fall zu visualisieren, kann man sich eine Person vorstellen, die willkürlich durch eine Stadt läuft. Die Stadt ist praktisch unendlich und in einem quadratischen Gitter von Bürgersteigen angeordnet. An jeder Kreuzung wählt die Person zufällig eine der vier möglichen Routen (einschließlich der ursprünglich befahrenen Route). Formal ist dies ein zufälliger Spaziergang auf der Menge aller Punkte in der Ebene mit ganzzahligen Koordinaten.

Wird die Person jemals zum ursprünglichen Ausgangspunkt der Wanderung zurückkehren? Dies ist das zweidimensionale Äquivalent des oben diskutierten Bahnübergangsproblems. 1921 bewies George Pólya, dass die Person mit ziemlicher Sicherheit einen zweidimensionalen Zufallsrundgang machen würde, aber ab drei Dimensionen sinkt die Wahrscheinlichkeit, zum Ursprung zurückzukehren, mit zunehmender Anzahl von Dimensionen. In 3 Dimensionen sinkt die Wahrscheinlichkeit auf ca. 34%

Zahlenwerte finden Sie unter http://mathworld.wolfram.com/PolyasRandomWalkConstants.html .

Mark L. Stone
quelle

21

Folgendes liegt den Mitwirkenden bei SciComp.SE am Herzen:

Die Navier-Stokes - Existenz und Glätte Problem

Die dreidimensionale Version ist natürlich ein bekanntes offenes Problem und Gegenstand eines millionenschweren Ton-Millenium-Preises. Aber die zweidimensionale Version wurde bereits vor langer Zeit mit einer positiven Antwort gelöst. Terry Tao stellt fest, dass die Lösung im Wesentlichen auf Lerays These von 1933 zurückgeht!

Warum ist das dreidimensionale Problem so viel schwieriger zu lösen? Die standardmäßige, von Hand gewellte Reaktion besteht darin, dass die Turbulenzen in drei Dimensionen erheblich instabiler werden als in zwei Dimensionen. Eine mathematisch genauere Antwort finden Sie in der offiziellen Problemstellung von Charles Fefferman am Clay Institute oder in Terry Taos netter Darstellung der möglichen Beweisstrategien .

Richard Zhang
quelle

20

In der Theorie der sozialen Wahl ist das Entwerfen eines Wahlschemas mit zwei Kandidaten einfach (Mehrheitsregeln), aber das Entwerfen eines Wahlschemas mit drei oder mehr Kandidaten erfordert zwangsläufig Kompromisse zwischen verschiedenen vernünftig klingenden Bedingungen. ( Unmöglichkeitssatz von Arrow ).

Ajd
quelle

11

$A_1$ $A_2$

U_{1}^{T} A_{1} V = Σ_{1}, U_{2}^{T} A_{2} V = Σ_{2}

$U_1^T A_1 V = \Sigma_1,\quad U_2^TA_2V=\Sigma_2$

Wenn jedoch die gleichzeitige Reduktion von drei Matrizen zu einer kanonischen Form (schwächere Bedingung als oben) erforderlich ist:

Q^{T} A_{1} Z = \tilde{A_{1}}, Q^{T} A_{2} Z = \tilde{A_{2}}, Q^{T} A_{3} Z = \tilde{A_{3}}

$Q^T A_1 Z = \tilde{A_1},\quad Q^T A_2 Z = \tilde{A_2},\quad Q^T A_3 Z = \tilde{A_3}$

(A_{1} + λ A_{2} + λ^{2} A_{3}) x = 0

$(A_1+\lambda A_2+\lambda^2 A_3)x=0$

Quelle: CF van Loan, "Vorlesung 6: Die generalisierte Singularwertzerlegung höherer Ordnung", CIME-EMS Summer School, Cetraro, Italien, Juni 2015.

Anton Menshov
quelle

U_{1}^{T}

$U_1^T$

U_{2}^{T}

$U_2^T$

V^{- 1}

$V^{-1}$

1

Σ

$\Sigma$

9

Es gibt viele Beispiele für Quantencomputer, obwohl ich schon eine Weile nicht mehr da bin und mich deshalb nicht mehr an viele erinnere. Ein wichtiger Punkt ist, dass die zweiteilige Verflechtung (Verflechtung zwischen zwei Systemen) relativ einfach ist, während die Verflechtung zwischen drei oder mehr Systemen ein ungelöstes Durcheinander mit wahrscheinlich hundert Artikeln ist, die zu diesem Thema verfasst wurden.

$\max\left(u_a v_b w_c T^{abc} / \left\lVert u \right\rVert \left\lVert v \right\rVert \left\lVert w \right\rVert \right)$

Dieses Papier scheint relevant zu sein, obwohl ich es nicht gelesen habe: Die meisten Tensorprobleme sind NP-hart

Dan Stahlke
quelle

2

Ich denke, das eigentliche Problem ist, dass die Tensorrangzerlegung für Tensoren der Ordnung 1 (Vektoren) und Tensoren der Ordnung 2 (Matrizen) einfach ist, für den Rest jedoch NP-schwer

Richard Zhang,

Das ist ein Teil davon, aber selbst wenn Sie eine Möglichkeit hatten, sie zu zerlegen, bleibt das Problem der Kategorisierung / Klassifizierung bestehen. Für die Verflechtung spielen lokale Unitaries keine Rolle, daher bleibt im Fall 2 nur eine Liste singulärer Werte (SVD wird in diesem Kontext als Schmidt-Zerlegung bezeichnet). Für höhere Bestellungen gibt es eine ganze Reihe von Möglichkeiten. Fragen wie, welche Zustände durch lokale Operationen in andere Zustände umgewandelt werden können, sind sehr schwierig (aus theoretischer Sicht, nicht unbedingt rechnerisch).

Dan Stahlke

5

Die Winkelhalbierung mit Lineal und Kompass ist einfach, eine Winkelteilung ist im Allgemeinen nicht möglich.

Davidhigh
quelle

4

Typinferenz für Rank-n-Typen . Die Typinferenz für Rang 2 ist nicht besonders schwierig, aber die Typinferenz für Rang 3 oder höher ist unentscheidbar.

André Popovitch
quelle

4

Hier ist ein schönes Beispiel aus der Optimierung: der ADMM-Algorithmus (Alternating Direction Method of Multipliers).

Bei einer entkoppelten und konvexen Zielfunktion zweier Variablen (die Variablen selbst könnten Vektoren sein) und einer linearen Beschränkung, die die beiden Variablen koppelt:

min f_{1} (x_{1}) + f_{2} (x_{2})

$\min f_1(x_1) + f_2(x_2)$

s . t . A_{1} x_{1} + A_{2} x_{2} = b

$s.t. \; A_1 x_1 + A_2 x_2 = b$

Die erweiterte Lagrange-Funktion für dieses Optimierungsproblem wäre dann

L_{ρ} (x_{1}, x_{2}, λ) = f_{1} (x_{1}) + f_{2} (x_{2}) + λ^{T} (A_{1} x_{1} + A_{2} x_{2} - b) + \frac{ρ}{2} | | A_{1} x_{1} + A_{2} x_{2} - b | |_{2}^{2}

$L_{\rho}(x_1, x_2, \lambda) = f_1(x_1) + f_2(x_2) + \lambda^T (A_1 x_1 + A_2 x_2 - b) + \frac{\rho}{2}|| A_1 x_1 + A_2 x_2 - b ||_2^2$

Der ADMM-Algorithmus führt grob eine "Gauß-Seidel" -Teilung der erweiterten Lagrange-Funktion für dieses Optimierungsproblem durch, indem zuerst in Bezug auf (während verbleiben minimiert wird fest), dann durch Minimieren von in Bezug auf (während fest bleiben), dann durch Aktualisieren von . Dieser Zyklus wird fortgesetzt, bis ein Stoppkriterium erreicht ist. $L_{\rho}(x_1, x_2, \lambda)$ $x_1$ $x_2, \lambda$ $L_{\rho}(x_1, x_2, \lambda)$ $x_2$ $x_1, \lambda$ $\lambda$

(Hinweis: Einige Forscher wie Eckstein verwerfen die Gauß-Siedel-Aufteilungsansicht zugunsten von proximalen Operatoren, siehe z. B. http://rutcor.rutgers.edu/pub/rrr/reports2012/32_2012.pdf. )

Bei konvexen Problemen hat sich gezeigt, dass dieser Algorithmus konvergiert - für zwei Variablensätze. Dies ist bei drei Variablen nicht der Fall. Zum Beispiel das Optimierungsproblem

min f_{1} (x_{1}) + f_{2} (x_{2}) + f_{3} (x_{3})

$\min f_1(x_1) + f_2(x_2) + f_3(x_3)$

s . t . A_{1} x_{1} + A_{2} x_{2} + A_{3} x_{3} = b

$s.t. \; A_1 x_1 + A_2 x_2 + A_3x_3 = b$

Selbst wenn alle konvex sind, kann die Konvergenz des ADMM-ähnlichen Ansatzes (Minimierung des Augmented Lagrangian in Bezug auf jede Variable , dann Aktualisierung der dualen Variablen ) NICHT garantiert werden, wie in diesem Artikel gezeigt wurde. $f$ $x_i$ $\lambda$

https://web.stanford.edu/~yyye/ADMM-final.pdf

Nathaniel Kroeger
quelle

3

Ein Stück Papier ohne Werkzeug in zwei Hälften zu falten ist einfach. Es ist schwer, es in Drittel zu falten.

Ein Polynom mit zwei Wurzeln zu faktorisieren ist einfach. Das Faktorisieren eines Polynoms mit drei Wurzeln ist wesentlich komplizierter.

Arkanist Lupus
quelle

3

Ihr erstes Beispiel entspricht nicht dem Sinn des Zitats. Die Idee ist, dass es schwieriger ist, ein Papier zu falten, wenn es nach zwei höher wird. Das Zitat hier wäre: "Gerade ist einfacher als ungerade". Ich denke, das zweite ist gut - und ich freue mich, wenn ich versuche, es mit dem Papier zu vereinfachen!

Bill K

3

Eine glatte Kurve des Grades 2 (dh gegeben als die Lösung von wobei ein Polynom des Grades 2 ist) mit einem gegebenen Punkt ist rational , was bedeutet, dass sie durch Quotienten von Polynomen des Grades parametrisiert werden kann 3 ist es nicht. Die ersteren werden als gut verstanden angesehen, die letzteren als elliptische Kurven, wenn ein Basispunkt, dh eine bestimmte Lösung, herausgegriffen wird, sind Gegenstand intensiver Forschung. $f(x,y) = 0$ $f$

Dieser Unterschied hat mehrere Auswirkungen:

In Stufe 2 gibt es Algorithmen, um alle rationalen Punkte zu finden (Lösungen in rationalen Zahlen), in Stufe 3 ist ein solcher Algorithmus nicht bekannt.
Integrale mit mit von Grad 1 oder 2 haben Lösungen in Elementarfunktionen, jedoch nicht für von Grad 3 oder höher. $\sqrt{f(x)}$ $f$ $f$
Das diskrete Logarithmusproblem ist auf Kurven des Grades 2 übertragbar, daher nicht für kryptografische Anwendungen geeignet, während die angenommene Härte desselben Problems auf elliptischen Kurven auf einigen der beliebtesten Kryptosysteme mit öffentlichem Schlüssel beruht.

doetoe
quelle

1

Die TREEFunktion.

Wir können rechnen TREE(2) = 3, sind aber TREE(3)im Universumsleben nicht berechenbar, wir wissen nur, dass es endlich ist.

nur zur Hälfte
quelle

TREE(3)Ist "kalkulierbar" genug Zeit gegeben. Beispielsweise könnten Sie für jedes alle farbigen Bäume der Größe generieren und prüfen, ob jedes die erforderlichen Kriterien erfüllt, bis keine solchen Bäume mehr vorhanden sind. Aber es würde unvorstellbar viel Raum und Zeit in Anspruch nehmen.

n

$n$

n

$n$

Setzen Sie Monica

Richtig, entschuldige den Fehler. Reparierte meine Aussage. Vielen Dank, Solomonoff!

Nur die Hälfte des

1

Zugehöriges Numberphile-Video zu Tree (3): youtube.com/watch?v=3P6DWAwwViU

Novice C

1

In einem zweidimensionalen Raum können Sie komplexe Strukturen einführen, mit denen sich viele Probleme (z. B. potenzielle Strömungsprobleme ) auf elegante Weise lösen lassen. In drei Dimensionen gibt es jedoch kein Analogon.

Patrick Sanan
quelle

0

In der Quantenvielkörperphysik untersuchen wir verschiedene Gitter von n Spins im Rahmen verschiedener Modelle (zB Heisenberg-Modell, Bose-Hubbard-Modell, Ising-Modell, ...). Sie haben natürlich verschiedene numerische Methoden, um sie zu studieren (DMRG, exakte Diagonalisierung, neuronale Netze, ...) und einer der Gründe, warum wir versuchen, verschiedene Methoden zu entwickeln, ist, dass Sie diese Modelle nicht lösen können, wenn n zu "hoch" wird. und es ist natürlich schlimmer, wenn du in höheren Dimensionen studierst. Für das Ising-Modell funktioniert beispielsweise die exakte Diagonalisierung in 1d für n nicht höher als 20. Für höheres n versuchen Sie also eine andere Methode: DMRG. Aber letztere funktionieren in der Tat gut für höheres n (wie n = 70, aber nicht gut für höheres n). Auch hier möchten Sie eine andere Methode für höhere n: neuronale Netze (dh künstliche Intelligenz). Und zusätzlich mit neuronalen Netzen, Sie können diese Modelle "leichter" (dh mit relativ höherem n) in höheren Dimensionen untersuchen (aber für Dimension = 3 und kleines n beispielsweise dauert es noch viele Stunden (mehrere Tage), um den Grundzustand oder das zu erhalten beobachtbar du wolltest ...). Bref, wenn n für Ihre numerischen Methoden (aber auch für die Kapazität Ihres Computers) "zu hoch" wird, müssen Sie neue Methoden ausführen (und wenn Sie können, verwenden Sie einen Supercomputer), und es ist das gleiche Problem mit der Dimension Ihres Computers System, aber natürlich schlimmer, da Sie schnell stecken bleiben (Dimension = 4 ist schwer zu bekommen, außer wenn Sie viel warten ...). Es dauert immer noch viele Stunden (mehrere Tage), um den Grundzustand oder das beobachtbare Objekt zu erhalten, das Sie wollten ...). Bref, wenn n für Ihre numerischen Methoden (aber auch für die Kapazität Ihres Computers) "zu hoch" wird, müssen Sie neue Methoden ausführen (und wenn Sie können, verwenden Sie einen Supercomputer), und es ist das gleiche Problem mit der Dimension Ihres Computers System, aber natürlich schlimmer, da Sie schnell stecken bleiben (Dimension = 4 ist schwer zu bekommen, außer wenn Sie viel warten ...). Es dauert immer noch viele Stunden (mehrere Tage), um den Grundzustand oder das beobachtbare Objekt zu erhalten, das Sie wollten ...). Bref, wenn n für Ihre numerischen Methoden (aber auch für die Kapazität Ihres Computers) "zu hoch" wird, müssen Sie neue Methoden ausführen (und wenn Sie können, verwenden Sie einen Supercomputer), und es ist das gleiche Problem mit der Dimension Ihres Computers System, aber natürlich schlimmer, da Sie schnell stecken bleiben (Dimension = 4 ist schwer zu bekommen, außer wenn Sie viel warten ...).
Natürlich sind es hier mehr zusätzliche Informationen zu Ihrer Frage, da in der Quantenvielkörperphysik n = 3 nicht hoch ist (aber wenn Sie ein Gitter nehmen, das ein Hyperwürfel ist, können Sie nicht n = 3 von Natürlich (wegen der Bedingungen)).

Albert B.
quelle

-3

Echte Welt:

Automatisierung% - zB Es ist einfach, etwas in 30% oder 50% oder 80% zu automatisieren, während es schwierig ist, zB über 95% zu gehen und unglaublich schwierig oder sogar fast unmöglich, 100% zu erreichen.

Joelty
quelle

2

Können Sie Referenzen für Ihre Ansprüche angeben?

nicoguaro

Ich kann nicht, aber schauen Sie sich zB selbstfahrende Autos an. Das Erlernen des Geradeausfahrens und der Geschwindigkeitskontrolle ist wahrscheinlich um ein Vielfaches einfacher als das Erlernen des normalen Fahrens. Je komplexer der Prozess ist, desto mehr Grenzfälle treten auf, wenn Sie ihn vollständig automatisieren

möchten

Dann denke ich, dass Ihre Frage für diese Site nicht geeignet ist.

nicoguaro

Gute Beispiele für „zwei sind einfach, drei sind schwer“ in den Computerwissenschaften

Antworten: