Beispiele für den Preis der Abstraktion?

112

Die theoretische Informatik hat einige Beispiele für "den Preis der Abstraktion" geliefert. Die beiden bekanntesten sind für die Gaußsche Eliminierung und Sortierung. Nämlich:

  • Es ist bekannt, dass die Gaußsche Elimination beispielsweise für die Berechnung der Determinante optimal ist, wenn Sie Operationen auf Zeilen und Spalten als Ganzes beschränken [1]. Offensichtlich hält sich Strassens Algorithmus nicht an diese Einschränkung und ist asymptotisch besser als die Gaußsche Elimination.
  • Wenn Sie beim Sortieren die Elemente der Liste als schwarze Kästchen behandeln, die nur verglichen und verschoben werden können, haben wir die standardmäßige informationstheoretische Untergrenze . Doch Fusionsbäume schlagen diese Grenze, soweit ich das verstehe, durch geschickte Verwendung von Multiplikation.nlogn

Gibt es noch andere Beispiele für den Abstraktionspreis?

Um ein bisschen formeller zu sein, suche ich nach Beispielen, bei denen eine Untergrenze in einem schwachen Berechnungsmodell unbedingt bekannt ist, in einem stärkeren Modell jedoch bekanntermaßen verletzt wird. Darüber hinaus sollte die Schwäche des schwachen Modells in Form einer Abstraktion vorliegen , die zugegebenermaßen ein subjektiver Begriff ist. Zum Beispiel betrachte ich die Beschränkung auf monotone Schaltkreise nicht als Abstraktion. Hoffentlich machen die beiden obigen Beispiele klar, wonach ich suche.

[1] KLYUYEV, VV und NI KOKOVKIN-SHcHERBAK: Zur Minimierung der Anzahl arithmetischer Operationen zur Lösung linearer algebraischer Gleichungssysteme. Übersetzung von GI TEE: Technischer Bericht CS 24, 4. Juni, t965, Abteilung Informatik, Universität Stanford.

Joshua Grochow
quelle
3
Ich mag diese Frage wirklich. Ich freue mich auf weitere Antworten.
Randomwalker
1
Es gibt auch "implizite" Abstraktionskosten. Sie erwähnen das Beispiel für den Preis der Abstraktion beim Sortieren und wie diese abstrahierten Ergebnisse nicht für das Sortieren von Zahlen gelten (was in manchen Fällen sogar in O (n) mit Bucketsort möglich ist). Untere Schranken von Voronoi-Diagrammen werden häufig abgeleitet, indem gezeigt wird, dass eine lineare Zeitverkürzung von einem Voronoi-Diagramm zum Sortieren einer Liste von Zahlen vorliegt. Viele geometrische Algorithmen leiten bei der Berechnung der Voronoi untere Schranken von dieser unteren Schranke ab.
Ross Snider
Warum ist das ein Community-Wiki?
Nanda
1
@nanda: Weil es keine einzige richtige Antwort gibt und die Frage in der Tat so gestaltet wurde, dass sie viele richtige Antworten liefert , wie ich glaube.
Joshua Grochow
1
Es scheint, als würden Sie sich wirklich auf Entspannung anstatt auf Abstraktion
beziehen

Antworten:

38

Ein weiteres schönes Beispiel für den Preis der Abstraktion: die Netzwerkkodierung . Es ist bekannt, dass in Multicast-Einstellungen die Max-Flow-Min-Cut-Beziehung nicht gleich ist (Primary und Dual stimmen nicht überein). Die traditionellen Modelle setzen jedoch einen Fluss voraus, der lediglich weitergegeben und in keiner Weise "verarbeitet" wird. Mit der Netzwerkcodierung können Sie diese Grenze umgehen, indem Sie Flows geschickt kombinieren. Dieses Beispiel war in erster Linie ein guter Motivator für das Studium der Netzwerkcodierung.

Suresh Venkat
quelle
33

Rein funktionale Programmierung ist eine populäre Abstraktion, die zumindest nach Ansicht ihrer Befürworter unter anderem eine deutliche Steigerung der Ausdruckskraft von Code bietet. Da es sich jedoch um ein restriktives Modell der Maschine handelt, das insbesondere keinen veränderlichen Speicher zulässt, stellt sich die Frage nach einer asymptotischen Verlangsamung im Vergleich zum üblichen Modell (RAM).

Zu dieser Frage gibt es hier einen tollen Thread . Die wichtigsten Imbissbuden scheinen zu sein:

  1. Sie können einen veränderlichen Speicher mit einem ausgeglichenen Binärbaum simulieren, daher ist die Verlangsamung im schlimmsten Fall O (log n).
  2. Bei eifriger Bewertung gibt es Probleme, bei denen dies das Beste ist, was Sie tun können.
  3. Bei der verzögerten Auswertung ist nicht bekannt, ob eine Lücke besteht oder nicht. Es gibt jedoch viele natürliche Probleme, für die kein bekannter rein funktionaler Algorithmus der optimalen RAM-Komplexität entspricht.

Es scheint mir, dass dies eine überraschend grundlegende Frage ist, die offen bleibt.

Randomwalker
quelle
Da die funktionale Programmierung ein Modell für umfangreiche Datenberechnungen ist (siehe MapReduce), ist diese Verlangsamung möglicherweise sehr bedeutend.
Suresh Venkat
5
Beachten Sie auch die im SO-Thread erwähnten Einschränkungen. Die untere Grenze von für ein Problem befindet sich in einem noch eingeschränkteren Modell: online mit atomaren Elementen. Ich glaube, eine Untergrenze dieser Form im Standardmodell der funktionalen Programmierung ist noch offen. Ω(nlogn)
Joshua Grochow
1
Zumindest das in diesem Thread erwähnte Papier ([Bird, Jones und De Moor, 1997], siehe dort für die vollständige Referenz) stellt eine Lücke zwischen eifriger und fauler Bewertung her.
Blaisorblade
Bei sehr großen Datenberechnungen sollten die E / A-Kosten so stark dominieren, dass logarithmische Verlangsamungen bei den Berechnungen keine Rolle spielen sollten, oder?
AdrianN
Was meinen Sie mit der Auswertungsreihenfolge?
Libeako
28

Während sich Ihre Frage auf die Komplexitätstheorie konzentriert, können ähnliche Dinge in anderen Bereichen wie der Theorie der Programmiersprachen passieren. Hier sind einige Beispiele, bei denen Abstraktion etwas Unentscheidbares macht (dh die Untergrenze im schwachen Modell ist unmöglich, während das starke Modell den Ausdruck des Algorithmus ermöglicht):

  • Im Lambda-Kalkül gibt es Funktionen, die Sie nicht direkt ausdrücken können (dh als Lambda-Term, der durch Beta auf das gewünschte Ergebnis reduziert wird). Ein Beispiel ist parallel oder (eine Funktion von zwei Argumenten, die dasjenige zurückgeben, das endet). Ein weiteres Beispiel ist eine Funktion, die ihr Argument buchstäblich ausgibt (eine Funktion kann offensichtlich nicht zwischen zwei Beta-äquivalenten Argumenten unterscheiden). Der Mangel an Ausdruckskraft ist darauf zurückzuführen, dass die Abstraktion erzwungen wird, dass Beta-äquivalente Lambda-Terme identisch behandelt werden müssen.

  • α,αα

Gilles
quelle
4
Ich wünschte, ich könnte dies mehrmals abstimmen.
Jacques Carette
26

Ω(m)mZn

Zn

MRA
quelle
25

stststminmax min+maxmin

Sei die Anzahl der Eckpunkte im Eingabediagramm. Es war bekannt, dass dieses Problem im Pfadvergleichsmodell von Karger, Koller und Phillips -Zeit benötigt , genau wie das Problem mit den kürzesten Pfaden für alle Paare. (Das Pfadvergleichsmodell unterstützt traditionelle Algorithmen wie Floyd-Warshall.) Im Gegensatz zu den kürzesten Pfaden aller Paare stellt sich jedoch heraus, dass Engpasspfade aller Paare in weniger als Zeit gelöst werden können schnelle Matrixmultiplikation.Ω ( n 3 ) O ( n 2,8 )nΩ(n3)O(n2.8)

Ryan Williams
quelle
22

Gemäß einer Diskussion in dieser Frage haben viele Probleme in der Berechnungsgeometrie untere Schranken im algebraischen Entscheidungsbaum oder in algebraischen Berechnungsbaummodellen, die auf fundamentalen Problemen wie Sortierung oder Elementunterscheidbarkeit beruhen . Es ist nicht schwer, Papiere zu finden, die behaupten, dass -Obergrenzen für verwandte Probleme wie die Konstruktion von Delaunay-Triangulationen optimal sind, weil sie mit diesen Untergrenzen übereinstimmen.O ( n log n )Ω(nlogn)O(nlogn)

Wenn die Eingabe jedoch in ganzzahligen kartesischen Koordinaten angegeben wird (wie dies in der Praxis häufig der Fall ist, da Gleitkommazahlen für die Berechnungsgeometrie nicht geeignet sind), stimmen diese unteren Grenzen nicht mit dem Berechnungsmodell überein. Es ist vielleicht nicht überraschend, dass Probleme mit orthogonalen Entfernungssuchtypen schneller mit Techniken gelöst werden können, die von der Ganzzahlsortierung übernommen wurden, aber auch nicht-orthogonale Probleme können häufig schnellere Algorithmen haben (die das Problem genau lösen, in Berechnungsmodellen, die Ganzzahlarithmetik mit O (1) ermöglichen ) mal die Genauigkeit der eingegebenen ganzen Zahlen). Siehe z. B. arXiv: 1010.1948 für eine Reihe von Beispielen.

David Eppstein
quelle
Vielen Dank für die Hervorhebung des "Paradoxons" und des kürzlich erschienenen Artikels von Chan und Pǎtraşcu.
András Salamon
17

Es gibt viele solcher Beispiele in der Kryptographie, insbesondere wissensfreie Beweise. Siehe zB die These:

Boaz Barak, Nicht-Black-Box-Techniken in der Kryptographie, 2003.

(Der Titel der Arbeit liefert übrigens einen wissensfreien Beweis für die Gültigkeit dieses Kommentars :)

Piotr
quelle
Bitte korrigieren Sie das
Zitierjahr
@ Sadeq Dousti: fertig. Es ist Community-Wiki und du hast mehr Ansehen als ich, also hättest du das wohl selbst korrigieren können ;-)
Blaisorblade
17

Algebraische Entscheidungsbäume werden als Grundlage in der Berechnungsgeometrie verwendet, um viele einfache Probleme aufzuzeigen, wie z. B. die Element-Eindeutigkeit . Diese Untergrenzen werden dann verwendet, um kompliziertere Probleme aufzuzeigen, wie Voronoi-Diagramme auch -Untergrenzen haben. Ich war dann später überrascht, einen erwarteten Zeitalgorithmus zum Lösen des nächsten Punktpaares in der Ebene zu lesen , was eine Verallgemeinerung der Element-Eindeutigkeit ist. Es entgeht dem durch Hashing gebundenen algebraischen Entscheidungsbaum. Ich habe es im Algorithm Design-Buch von Klein und Tardos gefunden. Es gibt einen ähnlichen, aber komplizierteren Algorithmus zum Lösen desselben Problems, der in RJ Liptons Blog beschrieben ist .Ω(nlogn)Ω(nlogn)O(n)

Referenz:

Kaveh
quelle
15

Berücksichtigen Sie synchrone deterministische verteilte Algorithmen, um die Anzahl der Farben in einem Zyklusdiagramm von auf zu reduzieren . Das heißt, Sie erhalten eine korrekte Farbe für den Zyklus und möchten eine korrekte Farbe für den Zyklus ausgeben. Jeder Knoten des Zyklus ist ein Prozessor.k3k3

Wenn Sie ein vergleichsbasiertes Modell annehmen (Sie behandeln die Farben als Blackboxes, die nur von einem Knoten zu einem anderen übertragen und miteinander verglichen werden können), erhalten Sie eine triviale Untergrenze von für die Anzahl von Kommunikationsrunden.kΩ(k)

Diese Abstraktion ist jedoch offensichtlich falsch: Wenn Sie etwas in einem Kommunikationsnetzwerk übertragen können, haben Sie eine Möglichkeit, "etwas" als Bitfolge zu codieren. Und jetzt sieht es viel besser aus.

Wenn Ihre Farben keine schwarzen Kästchen, sondern ganze Zahlen , können Sie die Farbreduzierung mithilfe von Cole-Vishkin-Techniken in -Kommunikationsrunden durchführen. Auch wenn Ihre Farben große Bit-Strings sind, wie Ganzzahlen von , erhalten Sie dasselbe gebundene .1,2,...,kO(logk)1,2,...,1010kO(logk)

Fazit: Der Preis für die "falsche" Abstraktion: vs. .Ω ( k )O(logk)Ω(k)

Jukka Suomela
quelle
13

Ein Beispiel, das mir in den Sinn kommt, ist die Berechnung des Volumens. Ein Ergebnis von Barany und Furedi ist, dass Sie eine exponentielle Anzahl von Abfragen benötigen und es einen zufälligen polynomiellen Zeitalgorithmus von Dyer-Frieze-Kannan gibt . Die Lücke repräsentiert den Preis der Abstraktion und auch den Vorteil der Zufälligkeit, aber ich denke, der Hauptgrund für die Lücke ist der Preis der Abstraktion. (Ich hoffe, ich habe die Frage verstanden und sie geht in die richtige Richtung.)

Gil Kalai
quelle
10

Dies ist wahrscheinlich nicht genau das, was Sie im Sinn hatten. Aber in gewissem Sinne ist die Unabhängigkeit von P gegen NP von Orakeln ein solches Beispiel. In Wirklichkeit heißt es, dass Sie diese Klassen nicht trennen oder reduzieren können, wenn Ihnen nur Simulation und Aufzählung am Herzen liegen (dh wenn dies Ihr "Modell" der Berechnung ist).

Ein konkreteres algorithmisches Beispiel ergibt sich aus der ungefähren Bereichssuche in der "umgekehrten" Richtung. Insbesondere werden die meisten Probleme bei der Bereichssuche als Halbgruppensummen ausgedrückt, und Unter- / Obergrenzen werden unabhängig von der Struktur dieser Halbgruppe ausgedrückt (mit Ausnahme einiger lichttechnischer Bedingungen). Neuere Arbeiten von Arya, Malamatos und Mount zeigen, dass Sie bei genauer Betrachtung der Halbgruppenstruktur (Eigenschaften von Idempotenz und Integralität) unterschiedliche (und engere) Grenzen für die ungefähre Entfernungssuche nachweisen können.

Suresh Venkat
quelle
4
Obwohl P gegen NP nicht das ist, was ich mir vorgestellt habe, ist es kein so schlechtes Beispiel. Übrigens schlagen Arora, Impagliazzo und Vazirani ( cseweb.ucsd.edu/~russell/ias.ps ) vor, dass die Schlüsseleigenschaft, die das allgemeine Orakelmodell abstrahiert, die lokale Überprüfbarkeit von Berechnungen ist. Insbesondere wenn ein Orakel die lokale Überprüfbarkeit und beibehält, dann ist , und wenn dann ist . Ihre Arbeit ist etwas umstritten (ich denke, sie führt zu Problemen bei der Relativierung kleinräumiger Klassen), aber ich finde sie sehr interessant. P XN P X P N P P X = N P X N P = c o N PXPXNPXPNPPX=NPXNP=coNP
Joshua Grochow
10

Der Shannon-Nyquist-Abtastsatz schlägt eine ausreichende Bedingung für informationstheoretische Grenzen der Kommunikation vor. In der Abtasttheorie werden Beispiele behandelt, bei denen das eingehende Signal eine kompakte / zufällige Darstellung aufweist. Jüngste Fortschritte bei der Stichprobenauswahl zeigen, dass diese Abstraktion möglicherweise mit einem Preis verbunden ist - dass die Dinge, die wir messen möchten, im Allgemeinen spärlich dargestellt werden, sodass diese Grenzen nicht eng sind. Außerdem können Informationen viel dichter codiert werden als ursprünglich angenommen.

  • Fehlerkorrekturcodes deuten darauf hin, dass die Shannon-Grenze in Netzwerklandschaften, die Rauschen ausgesetzt sind, teilweise neu bewertet wird.
  • Das brandneue Feld der Drucksensorik treibt die Rekonstruktion der verschiedenen Bilder voran, die wir über die Shannon-Grenze hinaus interessant finden.
Ross Snider
quelle
Kannst du dazu ein paar Hinweise geben :)?
Vivek Bagaria
8

Viele interessante naturwissenschaftliche Probleme erweisen sich im klassischen Sinne als NP-hart. Obwohl dieser Begriff theoretisch vollkommen gültig ist, hilft er dem Biologen oder Physiker in keiner Weise. Wir stellen fest, dass einige NP-schwierige Probleme mit festen Parametern behandelt werden können und häufig mit einem Parameter, der in der realen Welt durch eine kleine Konstante begrenzt wird.

Das heißt, TCS sagt uns, dass wir keine effiziente Lösung für das abstrakte Problem erwarten, aber tatsächlich auftretende Instanzen schnell lösen können - eine ziemliche Lücke.

Raphael
quelle
5

In diesem Artikel http://www.mimuw.edu.pl/~szymtor/papers/atom-turing.pdf haben wir Turing-Maschinen untersucht, die nur eingeschränkten Zugriff auf Daten haben. Dies wird formalisiert als invariant unter Automorphismen einer relationalen Struktur; In der unteren Grenze von O (n log n) für die Sortierung würde man beispielsweise sagen, dass die Maschine rationale Zahlen verarbeiten und speichern kann, aber ihre Übergänge sollten unter Automorphismen von (Q, <), dh monotonen Bijektionen, unveränderlich sein. Die formale Definition ist komplizierter, um genau zu spezifizieren, welche Art von Datenstrukturen die Maschine in ihrem Speicher speichern kann (sie sollte
in gewissem Sinne "endlich" sein , aber wir erlauben, kompliziertere Strukturen als nur Tupel von Datenwerten zu speichern, wie ungeordnete Tupel).

In der Arbeit haben wir einige Untergrenzen für andere Turing-Maschinen mit "eingeschränktem Datenzugriff" bewiesen. Insbesondere haben wir gezeigt, dass:

• Eine deterministische Turing-Maschine, die Vektoren verarbeiten kann (etwa über das Zwei-Elemente-Feld), aber nur Vektoradditions- und Gleichheitstests verwenden kann, kann in polynomieller Zeit nicht bestimmen, ob eine gegebene Liste von Vektoren linear abhängig ist (formal sollten die Maschinenübergänge sein) invariant sein unter Automorphismen des Vektorraums). Dies steht im Gegensatz zu nichtdeterministischen Maschinen, die einfach eine Kombination der Vektoren erraten können, die sich zu 0 addiert. Beachten Sie, dass die Gaußsche Eliminierung in polynomialer Zeit abläuft, aber Zugriff auf die Koordinaten der Vektoren hat. Insbesondere sind seine Übergänge unter Automorphismen des Vektorraums nicht invariant.

• In einem geeignet definierten Modell können Turing-Maschinen, die natürliche Zahlen nur in Bezug auf Gleichheit (nicht einmal <) vergleichen können, nicht bestimmt werden. Hier betrachten wir die relationale Struktur (N, =) und Maschinen, die unter ihren Automorphismen invariant sind. Es gibt eine Konstruktion (ähnlich der Cai-Furer-Immerman-Konstruktion aus der Finiten Modelltheorie), die zeigt, dass tatsächlich in diesem Modell P ≠ NP. Indem die Maschinen die Zahlen mit <vergleichen können, verfügen sie über ausreichende Leistung, um dies zu bestimmen.

Szymon Toruńczyk
quelle
2

In Black-Box-Frameworks wie der Komplexität von Entscheidungsbäumen oder der Komplexität von Quantenabfragen ist ein allgemeiner Abstraktionspreis vorhanden. Wenn wir die Analyse auf diese Modelle beschränken, können wir die Komplexität von Aufgaben oft sehr gut einschränken. Tatsächlich können wir bei der Quantenabfrage die Komplexität von Problemen grundsätzlich lösen, da die negative Gegnermethode enge Untergrenzen liefert (innerhalb eines Faktors von log n / log log n: 1005.1601 ). Dies gibt uns ein großartiges Werkzeug für die Analyse der Abfragekomplexität, aber es wird oft schwierig, die Abfragekomplexität mit der Zeit- / Raumkomplexität einer Standard-Turing-Maschine zu vergleichen (außer als grobe Untergrenze).

Artem Kaznatcheev
quelle
Haben Sie einige konkrete Beispiele dafür, wo dies eine Untergrenze gezeigt hat, die durch "Öffnen der Black Box" aufgehoben werden kann?
Joshua Grochow
Eine gute Sortierung ist ein Beispiel, bei dem das Entscheidungsbaummodell n log n ergibt. Sie können jedoch eine Verbesserung erzielen, indem Sie sich die Struktur der Eingabe ansehen.
Suresh Venkat
@ Suresh: Ich meinte Beispiele, die noch nicht erwähnt wurden :).
Joshua Grochow
es tut mir leid.
Suresh Venkat
Nun, manchmal kann man eine relativ nette Quantenabfragekomplexität haben, aber keinen schnell laufenden Algorithmus. Ein Beispiel ist das Problem der versteckten Untergruppen, bei dem wir eine polynomielle Anzahl von Abfragen benötigen, aber immer noch eine exponentielle Zeit (obwohl offensichtlich die untere Grenze der Zeit nicht bewiesen ist) für jeden bekannten Algorithmus [1]. Das ist ein Preis in die entgegengesetzte Richtung, denke ich. [1] arxiv.org/abs/quant-ph/0401083
Artem Kaznatcheev
1

Hier sind zwei Beispiele, die sich beide auf kontinuierliche vs. diskrete Modelle beziehen:

  1. Angenommen, es gibt einen (unendlich kleinen) Schatz, der im Intervall an Position versteckt ist . Wir wollen den Schatz durch Graben finden. Wann immer wir in Position graben , erhalten wir eine Rückmeldung, ob , oder . Wenn eine reelle Zahl sein kann, wird ein Suchalgorithmus möglicherweise nie beendet. mag sehr klein sein, aber wir kommen vielleicht nie zu . x y x < y x = y x > y x | x - y | y = x[0,1]xyx<yx=yx>yx|xy|y=x

    Wir können das Suchmodell jedoch erweitern, um ein kontinuierliches Kehren zu ermöglichen. In diesem Modell lassen wir einfach kontinuierlich über das -Intervall laufen und erhalten Feedback, wann immer .[ 0 , 1 ] y = xy[0,1]y=x

  2. Die Motivation für Problem A ergibt sich aus dem Problem der beneidungsfreien Kuchenteilung . Stromquist hat gezeigt , dass kein endliches Protokoll (auch wenn es unbegrenzt ist) eine beneidungsfreie Aufteilung eines Kuchens auf drei oder mehr Spieler garantieren kann, wenn jeder Spieler eine einzige zusammenhängende Figur erhalten soll.

    Wie Aumann und Dombb später erläuterten , gilt dieses Ergebnis jedoch nur für ein diskretes Schneidemodell, bei dem "In jedem Schritt wählt das Protokoll einen Spieler und eine reelle Zahl und fordert den Spieler auf, an dem eindeutigen Punkt eine Markierung vorzunehmen für die "," und nicht für Fälle, in denen beispielsweise ein Mediator vollständige Informationen über die Bewertungsfunktionen der Spieler hat und eine Aufteilung auf der Grundlage dieser Informationen vorschlägt ". & agr; i x v i ( 0 , x ) = αiαixvi(0,x)=α

    Darüber hinaus bezieht sich das Ergebnis nicht auf Algorithmen mit kontinuierlichem Betrieb, wie z. B. Verfahren mit beweglichen Messern.

Erel Segal Halevi
quelle
0

In der Logik erster Ordnung ausgedrückt, ist jeder Beweis des Pigeonhole-Prinzips für festes n exponentiell lang. Mit der Arithmetik kann der Beweis jedoch viel prägnanter ausgedrückt werden.

Der Erfolg von SMT-Solvern ist darauf zurückzuführen, dass das abstrakte Modell der Problemreduzierung auf SAT zurückgegangen ist, was es umfangreicheren Theorien ermöglicht, den Rechenaufwand erheblich zu reduzieren.

Arthur B
quelle