Które problemy

Słynny obraz świata Neila Immermana jest następujący (kliknij, aby powiększyć):

Jego „Naprawdę wykonalna” klasa nie obejmuje żadnej innej klasy; moje pytanie brzmi:

Co to jest problem AC ^0, który jest uważany za niepraktyczny i dlaczego?

cc.complexity-theory circuit-complexity Michaël Cadilhac
źródło

Może problem, który wymaga obwodów o głębokości 10 ^ {10 ^ 100}?

Tsuyoshi Ito

@ Ross: Nie sądzę, ponieważ nie wspomniał o „prawdziwym świecie” i zapytał „dlaczego”; Myślę, że mój poprzedni komentarz odpowiada przynajmniej na część „dlaczego”. Oczywiście nie mam przykładu „naturalnych” problemów, które występują w AC0 i wymagają obwodów o głębokości 10 ^ {10 ^ 100}.

Tsuyoshi Ito

Istnieje wiele interesujących problemów w świecie rzeczywistym, które można rozwiązać w stałym czasie i stałej przestrzeni (w praktycznie dowolnym modelu obliczeniowym), ale ludzie mają teraz pomysł, jak je rozwiązać w praktyce. Ekstremalne przykłady obliczają pewne stałe; moglibyśmy zakodować poprawną odpowiedź (np. 0 lub 1), ale jeszcze nie znamy odpowiedzi.

Jukka Suomela

Jukka: to są przypadki problemów. Równania diofantyczne (takie jak Fermata) są nierozstrzygalne jako klasa, nawet jeśli pojedyncze przypadki, które zdecydowaliśmy, mają obwody o stałej głębokości.

András Salamon,

@ András: Jeśli wolisz problemy decyzyjne z nieskończenie wieloma instancjami „tak” i „nie”: Niech

składa się ze wszystkich liczb parzystych i

, gdzie

jeśli biały gracz ma strategię wygraną w szachy, a poza tym

. Co prawda, istnieje bardzo prosta rodzina obwodów, która decyduje o

, ale nadal twierdzę, że jest to „niepraktyczne”. Nie dlatego, że obwód byłby ogromny, ale ponieważ zaprojektowanie obwodu byłoby ogromnym wysiłkiem obliczeniowym ... Oszukiwanie? -)

L

$L$

x

$x$

x = 1

$x = 1$

x = 3

$x = 3$

L

$L$

Jukka Suomela

Odpowiedzi:

Jeśli chcesz przykład funkcji AC ^0, która wymaga głębokości i nie może być obliczona przez obwody AC ⁰ o głębokości , wypróbuj funkcje Sipser . Indeks górny jest głębokość potrzebna do wielomianu wielkości AC ⁰ drukowanej. Z głębokością $d$ $d-1$ $S^{d,n}$ $d$ $d-1$ obwód wymagałby wykładniczo wielu bramek.

Zatem obliczenie dla nie byłoby „naprawdę wykonalne”. $S^{d,n}$ $d = 10^{10^{100}}$

EDYCJA: Twoje pytanie również pyta, dlaczego nie byłoby to wykonalne. Myślę, że powodem jest to, że to więcej niż liczba atomów we widzialnym wszechświecie. $10^{10^{100}}$

Robin Kothari
źródło

To wspaniale, dziękuję! Może możesz dodać nieformalną definicję funkcji Sipser? Nie wiedziałem o tym nazwisku.

Michaël Cadilhac

@ Michaël: Niestety nie mam dobrej intuicyjnej definicji funkcji Sipser. Chodzi o to, aby utworzyć funkcję kwantyfikatorów d, tak aby żaden obwód głębokości d-1 nie mógł jej obliczyć. Chcemy więc, aby kwantyfikatory d kwantyfikowały bardzo dużą liczbę zmiennych. Jest ładny artykuł autorstwa Iddo Tzamereta, zatytułowany „Håstad's Separation of Constant-Depth Circuits using Sipser Functions” ( itcs.tsinghua.edu.cn/~tzameret/SipserSwitching.pdf ), który definiuje funkcje formalnie na stronie 7.

Robin Kothari

Cała ta hierarchia jest celowo solidna przy wielomianowych zmianach wielkości wejściowej. Każda klasa w nim może zatem zawierać funkcje, których złożoność to powiedzmy n ^ {1000000000}, co byłoby teoretycznie „wykonalne”, ale na pewno nie praktycznie. Będą to jednak najprawdopodobniej bardzo sztuczne problemy. W szczególności za pomocą argumentu zliczającego istnieje rodzina formuły DNF (= obwody AC ^ 0 głębokość 2) o rozmiarze n ^ 1000000, której żaden algorytm, którego czas działania jest mniejszy niż n ^ 999999, nie jest w stanie obliczyć. (W jednolitym otoczeniu oczekujemy czegoś podobnego, ale nie możemy tego udowodnić.)

Noam
źródło

Problem zatrzymania, gdy wejście jest reprezentowane w jednostkowej, występuje w AC ^ 0, a jednak w rzeczywistości jest całkiem niewykonalny. Nie jestem pewien, o to ci chodziło, ale może to oznaczać Immerman.

Elad
źródło

Sądzę, że klasy na diagramie są zdefiniowane z pewnym pojęciem jednolitości? W przeciwnym razie kierunek w górę nie reprezentowałby zabezpieczenia, ponieważ P nie zawiera nierównomiernego AC ^ 0.

Robin Kothari,

A C^{0}

$AC^0$

{0, 1}

$\{0,1\}$

{0, m a x; X, B I T, \leq, =}

$\{0,max; X,BIT,\le,=\}$

X

$X$

Punkt dobrze przyjęty. Alternatywnie, po Erdos, można zamiast tego zasugerować problem, który dla dowolnego wejścia wypisuje liczbę Ramseya dla czerwonej szóstki i niebieskiej szóstki.

Elad