Genaue Komplexität eines Problems in

9

Sei $x_i \in \{-1,0,+1\}$ für $i \in \{1,\ldots,n\}$ mit dem Versprechen, dass $x = \sum_{i=1}^n{x_i} \in \{0,1\}$ (wobei die Summe über $\mathbb{Z}$ ). Wie komplex ist es dann zu bestimmen, ob $x = 1$ ?

Beachten Sie, dass das Problem trivial in $\cap_{m \geq 2}{\mathsf{AC}^0[m]}$ weil $x \equiv 1\bmod{m}$ iff $x = 1$ . Die Frage ist: Liegt das Problem in $\mathsf{AC}^0$ ? Wenn ja, wie sieht die Schaltung dies aus? Wenn nicht, wie beweist man das?

reference-request complexity-classes circuit-complexity upper-bounds SamiD
quelle

Dieses Problem mag trivial sein, aber ich kenne die Antwort nicht und wäre sehr daran interessiert, sie zu kennen.

SamiD

7

Sie können das übliche Switching-Lemma-Argument verwenden. Sie haben nicht erklärt, wie Sie Ihre Eingabe in Binärform darstellen, aber unter jeder vernünftigen Codierung ist die folgende Funktion AC äquivalent zu Ihrer Funktion: $^0$ (Wir nehmen an, dassist.)Nehmenwir an, dass Siediesen Vorlesungsnotizenfolgen

f (x_{1}, \dots, x_{n}) = {\begin{cases} 0 & wenn x_{1} - - x_{2} + x_{3} - - x_{4} + \dots - - x_{n} = 0, \\ 1 & wenn x_{1} - - x_{2} + x_{3} - - x_{4} + \dots - - x_{n} = 1, \\ ? & Andernfalls. \end{cases}

$f(x_1,\ldots,x_n) = \begin{cases} 0 & \text{if }x_1 - x_2 + x_3 - x_4 + \cdots - x_n = 0, \\ 1 & \text{if }x_1 - x_2 + x_3 - x_4 + \cdots - x_n = 1, \\ ? & \text{otherwise.} \end{cases}$

n

$n$

durch eine Tiefenschaltung

der Größe

berechnet werden kann. Danneine Zufalls Beschränkung

Eingänge Blätter eine Funktion der Entscheidungsbaum Komplexität höchstens

mitWahrscheinlichkeit von mindestens

f

$f$

d

$d$

n^{b}

$n^b$

n - n^{1 / 2^{d}}

$n - n^{1/2^d}$

2^{d} (b + 1) + 1

$2^d(b+1)+1$

. Eine Berechnung wird wahrscheinlich zeigen, dass dies eine weitere Instanz von

(bei einer kleineren Eingabegröße) mit der Wahrscheinlichkeit

1 - 1 / (3 n)

$1-1/(3n)$

f

$f$

, und so gibt es einige zufällige Restriktions die sowohl eine Instanz ergibt

auf

- Eingänge und eine Funktion mit konstanter Entscheidungsbaum Komplexität, zu einem Widerspruch führt. Das gleiche Argument sollte exponentielle Untergrenzen ergeben.

Θ (1 / \sqrt{n})

$\Theta(1/\sqrt{n})$

f

$f$

n^{1 / 2^{d}}

$n^{1/2^d}$

Yuval Filmus
quelle

Ich denke, die Gesamtempfindlichkeit dieser Funktion wird auch

, also könnten Sie das wahrscheinlich verwenden, um die exponentielle Untergrenze in meiner Antwort zu erhalten. Das Ergebnis, das ich dort zitiere, verwendet das Linial-Mansour-Nisan-Theorem, das selbst das Schalt-Lemma + einfache Grenzen für das Funktionsspektrum mit geringer Entscheidungsbaumkomplexität verwendet.

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

Sasho Nikolov

7

$\sum x_i = 0$ $\sum x_i = 2$ $x \in \{-1, 1\}^n$

$s$ $d$ $f: \{-1, 1\}^n \rightarrow \{0, 1\}$ $f(x) = \sum_i x_i$ $\sum_i x_i \in \{0,2\}$ $x$ $\sum_i x_i = 0$ $2^{-n} {n \choose n/2} \approx n^{-1/2}$ $x$ $n/2$ $f$ $f$ $\Omega(n^{1/2})$

s \geq 2^{Ω (n^{1 /. (2 d - - 2)})} .

$s \geq 2^{\Omega(n^{1/(2d-2)})}.$

Sasho Nikolov
quelle

Genaue Komplexität eines Problems in

Antworten: