Beispiele für den Preis der Abstraktion?

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.$n \log n$

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.

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.

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.

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.

• $\forall\alpha, \alpha\to\alpha$

$\Omega(\sqrt{m})$$m$$\mathbb{Z}_n^*$

$\mathbb{Z}_n^*$

$s$$t$$s$$t$$s$$t$$\min$max $+$$\max$$\min$

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$$\Omega(n^3)$$O(n^{2.8})$

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 $\Omega(n\log n)$$O(n\log n)$

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.

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 :)

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 .$\Omega(n \log n)$$\Omega(n \log n)$$O(n)$

Referenz:

• Richard J. Lipton, " Rabin Flips a Coin ", März 2009,
  veröffentlicht auf Godels Lost Letter und P = NP- Blog.

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.$k$$3$$k$$3$

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$$\Omega(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, ..., k$$O(\log^* k)$$1, 2, ..., 10^{10^k}$$O(\log^* k)$

Fazit: Der Preis für die "falsche" Abstraktion: vs. .Ω ( k $O(\log^* k)$$\Omega(k)$

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.)

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.

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.

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.

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.

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).

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 = $[0,1]$$x$$y$$x<y$$x=y$$x>y$$x$$|x-y|$$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 = $y$$[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$$\alpha$$i$$x$$vi(0,x) = \alpha$

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

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.