Monotone Schaltungskomplexität von Rechenfunktionen an spärlichen Eingängen

Das Gewichteiner binären Zeichenkette ist die Anzahl der Einsen in der Zeichenkette. Was passiert, wenn wir daran interessiert sind, eine monotone Funktion an Eingängen mit wenigen zu berechnen? $|x|$ $x\in\{0,1\}^n$

Wir wissen, dass die Entscheidung, ob ein Graph eine Klasse hat, für monotone Schaltkreise schwierig ist (siehe unter anderem Alon Boppana, 1987), aber wenn ein Graph beispielsweise höchstens Kanten hat, ist es möglich, einen monoton begrenzten Tiefenschaltkreis von zu finden Größe die Klasse entscheidet . $k$ $k^3$ $f(k)\cdot n^{O(1)}$ $k$

Meine Frage: Gibt es eine Funktion, die von einer monotonen Schaltung selbst bei Eingaben mit einem Gewicht von weniger als schwer zu berechnen ist $k$ ? Hier bedeutet hart Schaltkreisgröße $n^{{k}^{\Omega(1)}}$ .

Noch besser: es eine explizite monotone Funktion, die schwer zu berechnen ist, selbst wenn wir uns nur um Eingaben mit den Gewichten $k_1$ und $k_2$ ?

Emil Jeřábek hat bereits beobachtet, dass bekannte untere Schranken für monotone Schaltkreise gelten, die zwei Klassen von Eingängen trennen ( $a$ cliques vs maximal $(a-1)$ -colorable graphs), so dass es möglich ist, dies auf Kosten einer gewissen Unabhängigkeit des probabilistischen Arguments zu bewerkstelligen arbeiten für zwei Klassen von Eingaben mit festem Gewicht. Dies würde dazu $k_2$ , dass eine Funktion von $n$ die ich vermeiden möchte.

Was wirklich ist, ist eine explizite harte Funktion für $k_1$ und $k_2$ viel kleiner als $n$ (wie im Rahmen der parametrisierten Komplexität). Noch besser, wenn $k_1=k_2+1$ .

Beachten Sie, dass eine positive Antwort für eine exponentielle Untergrenze für beliebige Schaltungen implizieren würde. $k_1=k_2$

Update : Diese Frage ist möglicherweise teilweise relevant.

cc.complexity-theory lower-bounds circuit-complexity parameterized-complexity monotone MassimoLauria
quelle

Zu Ihrer allerersten (allgemeinen) Frage (nicht zu Clique). Ich denke, auch der Fall von Eingaben mit höchstens ist sehr schwierig. Nehmen Sie ein zweigeteiltes Graph mit . Ordnen Sie jedem Vertex eine boolesche Variable . Sei eine monotone Boolesche Funktion, deren Mintermen für die Kanten von . Sei die minimale Größe einer monotonen Schaltung, die an Eingängen mit Einsen korrekt berechnet . Dann gilt eine beliebige Untergrenze für eine Konstante

2

$2$

n \times m

$n\times m$

G

$G$

m = o (n)

$m=o(n)$

u

$u$

x_{u}

$x_u$

f_{G} (x)

$f_G(x)$

x_{u} \land x_{v}

$x_u\land x_v$

u v

$uv$

G

$G$

s (G)

$s(G)$

f_{G}

$f_G$

\leq 2

$\leq 2$

s (G) \geq (2 + c) n

$s(G)\geq (2+c)n$

c > 0

$c>0$ würde eine exponentielle Untergrenze für nichtmonotone Schaltkreise implizieren .

Stasys

Bestehende Argumente für monotone Schaltungen benötigen , die viele Eingänge mit vielen ( ) diejenigen , müssen zurückgewiesen . Das Beste, was wir bisher tun können, ist, die Untergrenze von zu beweisen , wenn die Schaltung alle Klassen akzeptieren und alle vollständigen partiten Graphen ablehnen muss ( ). Übrigens ist wichtig, dass Sie mit spärlichen , nicht mit dichten Eingaben umgehen . Sprich, -Clique erfordert etwa monotone Schaltungen der Größe für jede Konstante , aber -Clique hat monotone Schaltungen der Größe für jeden

≫ n / 2

$\gg n/2$

\exp (min {a, n / b}^{1 / 4})

$\exp(\min\{a,n/b\}^{1/4})$

b

$b$

a

$a$

a < b

$a<b$

k

$k$

n^{k}

$n^k$

k \geq 3

$k\geq 3$

(n - k)

$(n-k)$

O (n^{2} \log n)

$O(n^2\log n)$ Konstante .

k

$k$

Stasys

Ich sollte klarstellen, dass mir spärliche Eingaben im Sinne eines spärlichen Graphen wichtig sind. Die Suche nach einer Klasse in einem sehr spärlichen Graphen (mit beispielsweise Kanten) kann in der monotonen FPT-Schaltungsgröße durchgeführt werden.

k

$k$

k^{10}

$k^{10}$

MassimoLauria

Dein Beispiel im ersten Kommentar ist sehr schön. Wenn ich das richtig verstehe, ist dies ein ähnliches Problem mit monotonen Funktionen, die auf einem festen Gewicht hart sind . Bei Verwendung von Pseudo-Komplement-Funktionen zur Simulation negierter Eingänge unterscheidet sich die Schaltungskomplexität nicht zwischen monotonem und nicht monotonem Fall. Für konstantes (oder kleines) dieses Pseudokomplement durch eine monotone Schaltung effizient implementiert werden.

k

$k$

k

$k$

MassimoLauria

Mein erster Kommentar bezog sich auf die Komplexität der Grafiken. Das " " -Phänomen finden Sie auf Seite 13 dieses Entwurfs . Übrigens habe ich nicht ganz verstanden, was Sie unter "hart für k und k + 1" verstehen? (Meine Schuld natürlich.)

(2 + c) n

$(2+c)n$

Stasys

Unter besonderer Berücksichtigung eines Teils der Frage (z. B. für = 1, = 2) untersuchte Lokam in diesem Artikel die "2-Schicht" -Funktionen und beweist, dass starke untere Schranken für sie verallgemeinert werden können, daher ist dies ein sehr hartes offenes Problem in Bezug auf die grundlegende Trennung von Komplexitätsklassen und jede solche Konstruktion / explizite Funktion wäre ein Durchbruch; aus dem Abstract: $k_1$ $k_2$

Eine Boolesche Funktion f wird als 2-Slice-Funktion bezeichnet, wenn sie bei Eingängen mit weniger als zwei Einsen auf Null und bei Eingängen mit mehr als zwei Einsen auf Eins ausgewertet wird. Bei Eingängen mit genau zwei Einsen darf f nichttrivial definiert werden. Es gibt eine natürliche Korrespondenz zwischen 2-Schicht-Funktionen und Graphen. Unter Verwendung des Rahmens der Graphkomplexität zeigen wir, dass ausreichend starke superlineare monotone Untergrenzen für die sehr spezielle Klasse von 2-Schicht-Funktionen für bestimmte davon abgeleitete Funktionen über eine vollständige Basis superpolynome Untergrenzen implizieren würden.

Graphenkomplexität und Schichtfunktionen / Satyanarayana V. Lokam, Theory Comput. Systems 36, 71–88 (2003)

auch wie in seinen Kommentaren behandelt SJ diesen ähnlichen Fall in seinem Buch im Abschnitt über die Sternkomplexität von Graphen in Abschnitt 1.7.2.

Boolesche Funktionskomplexität: Fortschritte und Grenzen , Stasys Jukna

vzn
quelle

Monotone Schaltungskomplexität von Rechenfunktionen an spärlichen Eingängen

Antworten: