Fragen zu Untergrenzen von Funktionen, normalerweise zur Komplexität eines Algorithmus oder eines Problems
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...
Wenn ich einen Algorithmus für ein neues Problem entwerfe und nach einiger Zeit keinen Polynom-Zeit-Algorithmus mehr finde, kann ich versuchen, zu beweisen, dass er NP-schwer ist. Wenn es mir gelingt, habe ich erklärt, warum ich den Polynom-Zeit-Algorithmus nicht gefunden habe. Es ist nicht so,...
Was sind die besten Stromuntergrenzen für Zeit und Schaltkreistiefe für
In den 1980er Jahren hat Razborov gezeigt, dass es explizite monotone Boolesche Funktionen gibt (wie die CLIQUE-Funktion), für deren Berechnung exponentiell viele UND- und ODER-Gatter erforderlich sind. Die Basis {AND, OR} über der Booleschen Domäne {0,1} ist jedoch nur ein Beispiel für eine...
Lass PRIMES (aka Primality Testing ) das Problem sein: Gegeben eine natürliche Zahl , ist eine Primzahl?nnnnnn Lass FACTORING das Problem sein: In Anbetracht natürliche Zahlen , mit , ist einen Faktor mit ?nnnmmm1≤m≤n1≤m≤n1 \leq m \leq nnnnddd1<d<m1<d<m1 < d < m Ist bekannt, ob PRIMES...
Gier ist, mangels eines besseren Wortes, gut. Eines der ersten algorithmischen Paradigmen, die im Einführungskurs zu Algorithmen vermittelt werden, ist der gierige Ansatz . Gieriger Ansatz führt zu einfachen und intuitiven Algorithmen für viele Probleme in P. Interessanterweise führt der...
Vor einigen Jahren gab es eine Arbeit von Joel Friedman, die sich mit den unteren Schaltkreisgrenzen der Grothendieck-Kohomologie befasste (siehe Artikel: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024) ). Hat diese Denkrichtung neue Einsichten in die boolesche Komplexität...
Das kürzliche bahnbrechende Ergebnis von Ryan Williams zur Prüfung der Schaltungskomplexität in Bezug auf die Untergrenze bietet eine Beweismethode, bei der das Ergebnis der Obergrenze zum Nachweis der Komplexität in Bezug auf die Untergrenze verwendet wird. Suresh Venkat in seiner Antwort auf...
Sei eine Boolesche Funktion und betrachte f als eine Funktion von bis . In dieser Sprache ist die Fourier-Expansion von f einfach die Expansion von f in Form von quadratfreien Monomen. (Diese Monome bilden eine Basis für den Raum der reellen Funktionen auf . Die Summe der Quadrate der Koeffizienten...
Frage: Was ist die bekannteste untere Grenze der Formelgröße für eine explizite Funktion in AC 0 ? Gibt es eine explizite Funktion mit einem Ω ( n2)Ω(n2)\Omega(n^2) unteren Grenze von ? Hintergrund: Wie die meisten Untergrenzen sind auch Untergrenzen für die Formelgröße schwer zu bekommen. Ich...
Ich muss den laufenden Median berechnen: Eingabe: nnn , kkk , Vektor (x1,x2,…,xn)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) . Ausgabe: Vektor (y1,y2,…,yn−k+1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc, y_{n-k+1}) , wobei yiyiy_i der Median von (xi,xi+1,…,xi+k−1)(xi,xi+1,…,xi+k−1)(x_i, x_{i+1}, \dotsc, x_{i+k-1}) ....
Es ist klar, dass jedes Problem, das im deterministischen Lograum ( ) entscheidbar ist, höchstens zur Polynomzeit ( P ) auftritt . Zwischen L und P gibt es eine Fülle von Komplexitätsklassen . Beispiele umfassen N L , L o g C F L , N C i , S A C i , A C i , S C i . Es wird allgemein angenommen ,...
Ein Polynom f(x1,…,xn)f(x1,…,xn)f(x_1,\ldots,x_n) ist eine monotone Projektion eines Polynoms g(y1,…,ym)g(y1,…,ym)g(y_1,\ldots,y_m) wenn mmm = poly (n)(n)(n) , und es gibt eine Zuordnung π:{y1,…,ym}→{x1,…,xn,0,1}π:{y1,…,ym}→{x1,…,xn,0,1}\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\} so dass . Das...
Ich weiß, dass trivialerweise die OR-Funktion für Variablen genau durch das Polynom als solches dargestellt werden kann: , das vom Grad .nnn p ( x 1 , ... , x n ) p ( x 1 , ... , x n ) = 1 - ≤ n i = 1 ( 1 - x ix1, … , Xnx1,…,xnx_1,\ldots, x_np ( x1, … , Xn)p(x1,…,xn)p(x_1,\ldots,x_n) np ( x1, … ,...
Neben der (deterministischen) Kommunikationskomplexität einer Beziehung R ist die Protokollpartitionsnummer p p ( R ) ein weiteres grundlegendes Maß für den Kommunikationsbedarf . Die Beziehung zwischen diesen beiden Maßen ist bis zu einem konstanten Faktor bekannt. Die Monographie von Kushilevitz...
Im Anschluss an eine vorherige Frage , was sind die besten aktuellen Raum untere Schranken für SAT? Mit einer Leerzeichenuntergrenze meine ich hier die Anzahl der von einer Turing-Maschine verwendeten Arbeitsbandzellen, die ein binäres Arbeitsbandalphabet verwendet. Ein konstanter additiver Term...
In Anbetracht der jüngsten Kluft bei Tiefe-3 ergibt sich (was unter anderem eine Tiefen-3-Arithmetikschaltung für die Determinante über ergibt ), Ich habe folgende Fragen: Grigoriev und Karpinski haben eine Untergrenze für jede arithmetische Tiefen-3-Schaltung bewiesen, die die Determinante von...
Die genaue Formulierung des Titels stammt von Anand Kulkarni (der die Erstellung dieser Website vorgeschlagen hat). Diese Frage wurde als Beispielfrage gestellt, aber ich bin wahnsinnig neugierig. Ich weiß sehr wenig über algebraische Geometrie und verstehe die Hindernisse in der Frage P / Poly...
Präambel Interaktive Beweissysteme und Arthur-Merlin-Protokolle wurden bereits 1985 von Goldwasser, Micali, Rackoff und Babai eingeführt . Zuerst wurde angenommen, dass das erstere leistungsfähiger ist als das letztere, aber Goldwasser und Sipser zeigten, dass sie die gleiche Leistung haben ( in...
Unter Verwendung des Carry-Look-Ahead-Algorithmus können wir die Addition unter Verwendung einer Schaltkreisfamilie mit einer Polynomgrößentiefe von 5 (oder 4?) berechnen . Ist es möglich, die Tiefe zu verringern? Können wir die Addition von zwei Binärzahlen unter Verwendung einer...