Parität und

19

Parität und sind wie unzertrennliche Zwillinge. Zumindest scheint es seit 30 Jahren so. In Anbetracht von Ryans Ergebnissen wird das Interesse an den kleinen Klassen wieder zunehmen. $AC^0$

Fürst Saxe Sipser nach Yao nach Hastad gelten alle Paritäts- und Zufallsbeschränkungen. Razborov / Smolensky ist ein ungefähres Polynom mit Parität (ok, Mod Gates). Aspnes et al. Verwenden einen schwachen Grad an Parität. Außerdem setzen Allender Hertrampf und Beigel Tarui Toda für kleine Klassen ein. Und Rasborow / Beame mit Entscheidungsbäumen. All dies fällt in den Paritätskorb.

1) Was sind andere natürliche Probleme (abgesehen von der Parität), von denen direkt gezeigt werden kann, dass sie nicht in ? $AC^0$

2) Kennt jemand einen drastisch anderen Ansatz zur Untergrenze von AC ^ 0, der ausprobiert wurde?

cc.complexity-theory complexity-classes lower-bounds circuit-complexity V Vinay
quelle

13

Benjamin Rossmans Ergebnis auf für k-clique aus dem STOC 2008. $AC^0$

Verweise:

Paul Beame, " A Switching Lemma Primer ", Technischer Bericht 1994.
Benjamin Rossman, " Über die konstante Komplexität von k-Clique ", STOC 2008.

Kaveh
quelle

Fällt Rossman nicht unter Beames Grundierung, die auch eine Clique enthielt? Die Argumente sind natürlich komplizierter.

V Vinay

@V Vinay: Kannst du einen Link zu Paul Beames Artikel geben?

Kaveh

4

Rossmans Ergebnis zeigt, dass

Clique nicht mit Schaltkreisen konstanter Tiefe der Größe

berechnet werden kann . Beachten Sie, dass die Konstante im Exponenten nicht von der Tiefe der Schaltung abhängt. Hier wird die untere Grenze von Beames

verbessert .

k

$k$

Ω (n^{k / 4})

$\Omega(n^{k/4})$

n^{Ω (k / d^{2})}

$n^{\Omega(k/d^2)}$

Srikanth

@Srikanth, ich dachte, dass V Vinay sagt, dass Beame ein neueres Ergebnis hat, aber ich konnte keines auf seiner Seite finden. Danke für die Klarstellung.

Kaveh

1

Srikanth hat Recht, was die Grenzen angeht. Kaveh, keine neue Zeitung; Ich benutzte "subsumiert" in dem Sinne, dass ich Beame in meiner Frage aufgelistet hatte und mir daher der unteren Grenze der Clique bewusst war.

V Vinay

12

Es gibt den "Top-Down" -Ansatz von Håstad, Jukna und Pudlák, wie er in ihrem Artikel Top-Down-Untergrenzen für Strecken der Tiefe drei beschrieben ist . Leider ist es uns bisher nicht gelungen, den Ansatz auf höhere Tiefen auszudehnen.

Kristoffer Arnsfelt Hansen
quelle

Ja. Ich dachte , Sie von diesem Ansatz beeinflusst ein Papier hatte?

V Vinay

10

$AC^{0}$

2) Ein topologische Ansatz wieder nur für Tiefe drei Schaltungen arbeitet, wurde von vorgeschlagenen Kriegel und Waack .

Alessandro Cosentino
quelle

2

Mehrheit ist die gleiche Sache wirklich. Ich habe es aber erwähnt habe. Auch gab es ein Papier von Boppana Majority in der Mitte der 80er Jahre.

V Vinay

8

Die anderen beiden "klassischen" Methoden sind Haken's Bottleneck-Methode und Karchmer's Fusion-Methode (so genannt von Avi Wigderson), die beide in der monotonen Einstellung viel einfacher anzuwenden sind.

Yuval Filmus
quelle

Parität und

Antworten: