AC (složitost) - AC (complexity) - Wikipedia

v složitost obvodu, AC je třída složitosti hierarchie. Každá třída ACⁱ, se skládá z jazyky uznán Booleovské obvody s hloubkou ${ displaystyle O ( log ^ {i} n)}$ a a polynomiální číslo z neomezený fan-in A a NEBO brány.

Název „AC“ byl vybrán analogicky k NC, přičemž „A“ ve jménu znamená „střídavý“ a odkazuje na střídání mezi branami AND a OR v obvodech a na střídavé Turingovy stroje.^[1]

Nejmenší třída AC je AC⁰, skládající se z neomezených fan-in obvodů s konstantní hloubkou.

Celková hierarchie tříd AC je definována jako

${ displaystyle { mbox {AC}} = bigcup _ {i geq 0} { mbox {AC}} ^ {i}}$

Vztah k NC

Třídy AC se vztahují k NC třídy, které jsou definovány podobně, ale s branami, které mají pouze konstantní fanin. Pro každého i, my máme^[2][3]

${ displaystyle { mbox {NC}} ^ {i} subseteq { mbox {AC}} ^ {i} subseteq { mbox {NC}} ^ {i + 1}.}$

Okamžitým důsledkem toho je NC = AC.^[4]

Je známo, že začlenění je přísné i = 0.^[3]

Variace

Výkon tříd AC lze ovlivnit přidáním dalších hradel. Pokud k tomu přidáme brány, které vypočítají modulo provoz pro nějaký modul m, máme třídy ACCⁱ[m].^[4]

Poznámky

Reference

• Arora, Sanjeev; Barak, Boaz (2009), Výpočetní složitost. Moderní přístup, Cambridge University Press, ISBN  978-0-521-42426-4, Zbl  1193.68112
• Clote, Peter; Kranakis, Evangelos (2002), Booleovské funkce a výpočetní modely, Texty v teoretické informatice. Série EATCS, Berlín: Springer-Verlag, ISBN  3-540-59436-1, Zbl  1016.94046
• Regan, Kenneth W. (1999), „Třídy složitosti“, Příručka Algoritmy a teorie výpočtu, CRC Stiskněte.
• Vollmer, Heribert (1998), Úvod do složitosti obvodů. Jednotný přístup„Texty z teoretické informatiky, Berlín: Springer-Verlag, ISBN  3-540-64310-9, Zbl  0931.68055