Monotone Rechenschaltungen

Der Stand unseres Wissens über allgemeine arithmetische Schaltkreise scheint dem Stand unseres Wissens über boolesche Schaltkreise ähnlich zu sein, dh wir haben keine guten Untergrenzen. Andererseits haben wir Exponentialgrößenuntergrenzen für monotone Boolesche Schaltungen .

Was wissen wir über monotone Rechenschaltungen? Haben wir ähnliche gute Untergrenzen für sie? Wenn nicht, was ist der wesentliche Unterschied, der es uns nicht ermöglicht, ähnliche Untergrenzen für monotone Arithmetikschaltungen zu erhalten?

Die Frage wurde durch Kommentare zu dieser Frage inspiriert .

Niedrigere Schranken für monotone arithmetische Schaltkreise sind einfacher, weil sie Stornierungen verbieten. Andererseits können wir exponentielle Untergrenzen für Schaltkreise, die Boolesche Funktionen berechnen, auch dann nachweisen, wenn monotone reelle Funktionen $g:R\times R\to R$ als Gatter zulässig sind (siehe z. B. Abschn. 9.6 im Buch ).

$a\land a=a$$a\lor (a\land b)=a$( + , max $(+,\min)$$(+,\max)$. Die Gatter entsprechen dann den vom Algorithmus verwendeten Teilproblemen. Was Jerrum und Snir (in dem Aufsatz von V Vinay) tatsächlich beweisen, ist, dass jeder DP-Algorithmus für das Min Weight Perfect Matching (sowie für das TSP-Problem) exponentiell viele Unterprobleme erzeugen muss. Das Perfect Mathching-Problem ist jedoch kein "DP-Fehler" (es entspricht nicht Bellmans Optimalitätsprinzip ). Die lineare Programmierung (nicht DP) ist für dieses Problem viel besser geeignet.

Also , was über Optimierungsprobleme , die kann durch relativ klein DP Algorithmen gelöst werden - können wir beweisen , untere Schranken für sie auch? Sehr interessant in dieser Hinsicht ist ein altes Ergebnis von Kerr (Satz 6.1 in seiner Doktorarbeit ). Dies impliziert, dass der klassische Floyd-Warshall-DP-Algorithmus für das All-Pairs Shortest Paths-Problem (APSP) optimal ist : -Unterprobleme sind erforderlich. Noch interessanter ist, dass Kerrs Argument sehr einfach ist (viel einfacher als das von Jerrum und Snir verwendete): Es wird nur das Verteilungsaxiom und die Möglichkeit, Min-Gates zu "töten", indem eines ihrer Argumente auf Auf diese Weise beweist er, dassa + min ( b , c ) = min ( a , b ) + min ( a , c ) 0 n 3 n × n ( + , min $\Omega(n^3)$$a+\min(b,c)=\min(a,b)+\min(a,c)$$0$$n^3$Plus-Gatter sind notwendig, um zwei Matrizen über das Semiring zu multiplizieren . In Abschn. In 5.9 des Buches von Aho, Hopcroft und Ullman wird gezeigt, dass dieses Problem dem APSP-Problem entspricht.$n\times n$$(+,\min)$

Eine nächste Frage könnte lauten: Was ist mit dem Problem der Single-Source Shortest Paths (SSSP)? Der Bellman-Ford-DP-Algorithmus verwendet für dieses (scheinbar "einfachere") Problem auch -Tore. Ist das optimal? Bisher ist keine Trennung zwischen diesen beiden Versionen des Problems des kürzesten Pfades bekannt; siehe eine interessante Arbeit von Virginia und Ryan Williams in dieser Richtung. Eine -Untergrenze in -Kreisläufen für SSSP wäre also ein großartiges Ergebnis. Die nächste Frage könnte lauten: Was ist mit den Untergrenzen für Knapsack? In diesem Entwurf werden untere Schranken für Knapsack in einem schwächeren Modell von Kreisen bewiesen, in denenΩ ( n 3 ) ( + , min ) ( + , max ) $O(n^3)$$\Omega(n^3)$$(+,\min)$$(+,\max)$$+$-tore ist eingeschränkt; im Anhang ist Kerrs Beweis wiedergegeben.

Ja. Wir kennen gute untere Schranken und wir kennen sie seit einiger Zeit.

Jerrum und Snir bewiesen 1980 eine exponentielle Untergrenze über monotonen Arithmetikkreisen für die bleibende Karte. Valiant zeigte, dass sogar ein einzelnes Minus-Gatter exponentiell mächtiger ist .

Weitere Informationen zu (monotonen) Rechenschaltungen finden Sie in Shpilkas Umfrage zu Rechenschaltungen .

Ein weiteres Ergebnis , dass ich bin mir dessen bewusst ist durch Arvind, Joglekar und Srinivasan - sie gegenwärtig explizit Polynome berechenbar durch lineare Größe breiten- monotone Rechenschaltungen aber jede breiten- monoton arithmetische Schaltung würde exponentiellen Größe nehmen.$2k$$k$

Ist diese Zählung: Chazelle semi-Gruppe Untergrenzen für grundlegenden Entfernungs-Suche Probleme (in der Offline - Einstellung). Alle Untergrenzen sind nahezu optimal (bis zu logarithmischen Ausdrücken, wenn die Untergrenze polynomisch ist, und logarithmischen Ausdrücken, wenn die Untergrenze polylogarithmisch ist).