AC0 - AC0

Schéma AC0 obvod: n vstupních bitů je na spodní straně a horní brána produkuje výstup; obvod se skládá z bran AND- a OR bran polynomiálního fan-inu a hloubka střídání je omezena konstantou.

AC0 je třída složitosti použito v složitost obvodu. Je to nejmenší třída v AC hierarchie a skládá se ze všech rodin obvodů hloubky O (1) a velikosti polynomu, s neomezenýmfanin A brány a NEBO brány. (Dovolujeme NE brány pouze na vstupech).[1] Obsahuje tedy NC0, který má pouze ohraničené-faninové brány AND a OR.[1]

Ukázkové problémy

Sčítání a odčítání celých čísel lze vypočítat v AC0,[2] ale násobení není (alespoň ne pod obvyklými binárními nebo základními 10 reprezentacemi celých čísel).

Jelikož se jedná o třídu obvodů, jako P / poly, AC0 také obsahuje všechny unární jazyk.

Popisná složitost

Od a popisná složitost hledisko, DLOGTIME -jednotný AC0 se rovná popisné třídě FO + BIT ze všech jazyky popsatelné v logice prvního řádu s přidáním BIT predikát, nebo alternativně FO (+, ×) nebo Turingův stroj v logaritmická hierarchie.[3]

Separace

V roce 1984 Furst, Saxe a Sipser ukázal, že výpočet parita o vstupu nelze rozhodnout žádným AC0 obvody, dokonce s nejednotností.[4][1]Z toho vyplývá, že AC0 se nerovná NC1, protože rodina obvodů ve druhé třídě může počítat paritu.[1] Z toho plynou přesnější hranice přepínání lemmatu. Při jejich používání se ukázalo, že existuje věštecké oddělení mezi polynomiální hierarchie a PSPACE.

Reference

  1. ^ A b C d Arora, Sanjeev; Barak, Boaz (2009). Výpočetní složitost. Moderní přístup. Cambridge University Press. str.117 –118, 287. ISBN  978-0-521-42426-4. Zbl  1193.68112.
  2. ^ Barrington, David Mix; Maciel, Alexis (18. července 2000). „Přednáška 2: Složitost některých problémů“ (PDF). IAS / PCMI Summer Session 2000, Clay Mathematics Undergraduate Program: Basic Course on Computational Complexity.
  3. ^ Immerman, N. (1999). Popisná složitost. Springer. p.85.
  4. ^ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parita, obvody a hierarchie polynomiálního času". Teorie matematických systémů. 17 (1): 13–27. doi:10.1007 / BF01744431. PAN  0738749. Zbl  0534.94008.