Rechenschaltungskomplexität von Entscheidungsproblemen

9

Hat jemand untersucht, wie komplex klassische Entscheidungen wie Primes oder Graph-Isomorphism für kleine Eingangsgrößen ? $N$

Während die meisten Leute daran interessiert sind, wie die Skalierung als , wäre es meiner Meinung nach auch interessant zu sehen, wie dies für kleine N wächst. Sicher, wir wissen jetzt, dass Primes in P ist, aber es wäre ordentlich Sehen Sie, wie es wächst, und vielleicht sogar starke Änderungen in der Wachstumsrate des Diagramms, wenn die Eingaben groß genug werden, dass ein anderer Algorithmus effizienter wird. $N \to \infty$

Es besteht sogar die (unwahrscheinliche) Möglichkeit, dass jemand aus einer Folge von Schaltkreisen einen allgemeinen Algorithmus extrahiert.

Es scheint, als könnte dieser Ansatz andere Fragen beantworten , als normalerweise zu . Mit den Fortschritten des Algorithmuswissens (SAT-Löser usw.) und der Super-Rechenleistung konnten konkrete Antworten für kleine . $N \to \infty$ $N$

Gibt es Referenzen oder Ergebnislisten für Personen, die explizit die Schaltungskomplexität von Entscheidungsproblemen für kleine berechnen ? $N$

Wenn Leute daran arbeiten, welche Algorithmen verwenden sie derzeit, um das Problem der minimalen Schaltung zu lösen (geben Sie bei gegebener Boolescher Funktion und Satz von Gattern eine Schaltung mit der minimalen Anzahl von erforderlichen Gattern aus)?

cc.complexity-theory reference-request circuit-complexity TigerSpots
quelle

Es scheint nahezu unmöglich zu sein, aus dieser Richtung anzugreifen, da nicht einmal optimale Schaltungen für sehr "kleine" Probleme berechnet werden können. Dies scheint im Grunde ein Ergebnis der Komplexität von Kolmogorov zu sein. Eine andere scheinbar vielversprechende / äquivalente Richtung, die nicht sehr bekannt oder viel untersucht ist, ist die Komplexität von Graphen, die das Studium "kleinerer" Probleme zu ermöglichen scheint, aber immer noch große Auswirkungen hat, z. B. auf die Trennung von Komplexitätsklassen ... auch bekannt als "sogenanntes" Vergrößerungs-Lemma ". etc

vzn

7

Ja, das ist eine natürliche Idee und die Leute haben darüber nachgedacht. Kurz gesagt, das Problem ist, dass selbst die SAT / QBF-Löser nach dem Stand der Technik nur sehr kleine Schaltkreise (mit etwa 10 bis 12 Gattern) finden können, ganz zu schweigen davon, dass es keinen kleinen Schaltkreis gibt. Einige Referenzen:

Ryan Williams, Anwendung der Praxis auf die Theorie (2008):

Unser Wissen über die Komplexität boolescher Schaltungen ist ziemlich schlecht. <…> Ein guter Grund, warum wir nicht viel über die wahre Leistung von Schaltkreisen wissen, ist, dass wir nicht viele Beispiele für minimale Schaltkreise haben. Wir wissen zum Beispiel nicht, wie eine optimale Schaltung für die Boolesche Matrixmultiplikation aussieht. $3 \times 3$

Ein guter Grund, warum wir nicht viel über die wahre Leistung von Schaltkreisen wissen, ist, dass wir nicht viele Beispiele für minimale Schaltkreise haben. Wir wissen zum Beispiel nicht, wie eine optimale Schaltung für die Boolesche Matrixmultiplikation aussieht. <…> Könnten wir von einer Enzyklopädie der Mindestschaltungen profitieren? Was machen zum Beispiel die kleinsten Booleschen Schaltkreise für $3 \times 3$ $10 \times 10$ Boolesche Matrixmultiplikation sieht aus wie? Sind sie regelmäßig aufgebaut? Es ist wahrscheinlich, dass die Antworten wertvolle Einblicke in die Komplexität des Problems geben. Die besten uns bekannten Algorithmen reduzieren das Problem auf die Matrixmultiplikation über einen Ring, die dann durch eine sehr regelmäßige, rekursive Konstruktion (wie Strassens [Str69]) gelöst wird. Selbst wenn die katalogisierten Schaltkreise nicht wirklich minimal sind, aber nahe daran liegen, könnten konkrete Beispiele für kleine Eingaben nützlich sein, damit Theoretiker nach Inspiration suchen oder Computer, um mithilfe maschineller Lerntechniken nach Mustern zu suchen. Die Kraft kleiner Beispiele ist nicht zu unterschätzen.

Experimente mit QBF-Lösern haben noch keine signifikanten neuen Erkenntnisse ergeben. Bisher haben sie eine Tatsache entdeckt: Die optimale Größenschaltung für die Boolesche Matrixmultiplikation ist die offensichtliche. Nun, duh. Was ist mit dem Fall? Das ist schon schwierig! Der sKizzo QBF-Solver [Ben05] kann beweisen, dass es für keine Schaltung mit 10 Gates gibt, aber nichts darüber hinaus. Selbst wenn wir die Gates auf Fan-In Two beschränken, stürzt der Solver bei größeren Instanzen ab. $2 \times 2$ $3 \times 3$ $3 \times 3$

Zusammen mit Evgeny Demenkov, Arist Kojevnikov und Grigory Yaroslavtsev ist es uns gelungen, mit SAT-Solvern die Obergrenzen für die Schaltungsgröße symmetrischer Funktionen zu verbessern. Details finden Sie in den folgenden beiden Abhandlungen: Finden effizienter Schaltkreise mithilfe von SAT-Solvern (2009), Neue Obergrenzen für die Komplexität boolescher Schaltkreise symmetrischer Funktionen (2010). Wir kennen jedoch die genaue Schaltungskomplexität für viele Elementarfunktionen nicht: zum Beispiel , .

2.5 n \leq C (M O D_{3}) \leq 3 n

$2.5n \le C(MOD_3) \le 3n$

2 n \leq C (A N D, O R, X O R) \leq 2.5 n

$2n \le C(AND,OR,XOR) \le 2.5n$

In den Übungen 477–481 in Abschnitt 7.2.2.2: Erfüllbarkeit von TAOCP Volume 4 von Don Knuth (2015) werden Möglichkeiten zur Suche nach optimalen Schaltkreisen mithilfe von SAT-Lösern erörtert. Von der Lösung zur Übung 481:

Es ist wahr für . Hier ist eine 12-stufige Berechnung mit und , die 2014 von Armin Biere gefunden wurde: <…> Der Fall und , der quälend nahe an den Grenzen der heutigen Löser liegt, ist noch unbekannt . $n \le 5$ $n=6$ $a=0$ $n=6$ $a \neq 0$

Alexander S. Kulikov
quelle

5

In vielen ungleichmäßigen Modellen - Boolesche Schaltungen, algebraische Schaltungen, Entscheidungsbäume, Verzweigungsprogramme usw. - scheint die Berechnung der genauen Komplexität erheblich schwieriger zu sein als die Berechnung der asymptotischen Komplexität. Ich hoffe zwar, dass Ihre Intuition korrekt ist - dass das Verständnis der genauen Komplexität kleiner Instanzen zu asymptotischen Einsichten führen kann -, aber ich kenne nur wenige Fälle, in denen dies geschehen ist:

Algorithmen und Untergrenzen für die Matrixmultiplikation kleiner Formate. An 2x2 ( Strassen ), 3x3 ( Laderman ) und anderen kleinen Formaten für die Matrixmultiplikation wurde viel gearbeitet (siehe auch Johnson-McLoughlin und Hopcroft-Kerr ). Ursprünglich konnten diese aufgrund der rekursiven Struktur der Matrixmultiplikation häufig verwendet werden, um asymptotische Verbesserungen zu erzielen. Schließlich verdrängte Coppersmith-Winograd all dies im asymptotischen Bereich.
GCT-artige Untergrenzen bei der Multiplikation kleiner Matrix aufgrund von Bürgisser und Ikenmeyer haben asymptotische Untergrenzen bei der Matrixmultiplikation ergeben. Ich denke, dies liegt zumindest teilweise daran, dass die darstellungstheoretische Struktur natürlich nahe legt, wie eine einzelne, exakte Untergrenze in eine unendliche Familie umgewandelt werden kann.
(Siehe Alexander Kulikovs Antwort für ein paar weitere)

Abgesehen davon gab es eine kleine, aber nicht triviale Menge an Arbeiten zur genauen Komplexität verschiedener Probleme, aber meistens Probleme, die einfacher sind als GraphIso oder Primes (mit Ausnahme des letzten Beispiels der permanenten). Ich finde diese Arbeit zwar interessant und hoffe, dass sie zu größeren theoretischen Einsichten führen wird, soweit ich weiß, dass dies noch nicht geschehen ist.

Knuth befasste sich in Kapitel 5, Band 3 mit der Frage nach der genauen Anzahl der Vergleiche, die zum Sortieren einer Liste von Elementen erforderlich sind . 3 von TAOCP . Seitdem wurden weitere Fortschritte erzielt (siehe die Arbeit von Peczarski und die darin enthaltenen Referenzen). $n$
Es wurden auch einige Arbeiten zu Sortiernetzwerken mit exakter Mindesttiefe durchgeführt ( Bundala und Závodný scheinen die neuesten zu sein).
Bei genauer Komplexität kann es aufgrund der Größe der Eingabe zu zahlentheoretischen Effekten kommen. (Wenn es sich beispielsweise um einen Divide-and-Conquer-Algorithmus handelt, kann man sich leicht vorstellen, wie sich Eingaben der Größe von Eingaben der ungeraden Größe unterscheiden können, wenn es um die genaue Komplexität geht.) Beispiele hierfür finden Sie in Drmota und Szpankowski sowie einen genauen Hauptsatz. $2^k$
Determinante Komplexität kleiner bleibender (obere Grenze von B. Grenet und jüngste untere Grenze von von Alper, Bogart und Velasco ) und anderer Funktionen ( Qiao, Sun und Yu ). $per_3$

Joshua Grochow
quelle

Rechenschaltungskomplexität von Entscheidungsproblemen

Antworten: