AC 0

A komplexitás elmélet , AC 0 olyan bonyolultsági osztály által meghatározott logikai áramkörök állandó mélységben. Ez az AC hierarchia része . Az AC 0 osztály tartalmaz összeadást, de nem tartalmazza a paritásfüggvényt, a szorzást vagy az elsődleges predikátumot (lásd alább).

Meghatározás

Az osztály AC 0 a bonyolultsági osztály a problémák határozzák meg logikai áramkörök állandó mélység, többtagú méret, a kapuk és és OR , fok beérkező határtalan (sőt a többi ajtó is engedélyezhető, mint a „ kizáró vagy ” vagy NEM kapuk , mert kifejezhető, a bonyolultság megváltoztatása nélkül, AND és OR segítségével ). Az AC rövidítés váltakozó áramkörből származik . Ez az AC hierarchia része .

Példák

Az összeadás AC 0-ban van . Pontosabban, minden i esetében az a döntési probléma, amely 2n bit bemenetként veszi fel az n bit két a és b számát, és amely kiszámítja az a és b összegének i- edik bitjét, AC 0-ban van .

Részletek egy polinom méretű és állandó mélységű áramkörről az összeadáshoz

Így állíthatunk össze egy áramkört az n-1 ... a 0 és b n-1 ... b 0 összegének i- edik bitjének kiszámításához . Vegye figyelembe a ∧ "és" logika, ∨ a logikai "vagy" és ⊕ kizárólagos vagy. J- t tételként tekintünk igaznak, ha az a j- edik bitje 1-gyel egyenlő, és hamis egyébként. Hasonlóképpen, b j mint tétel, akkor igaz, ha a b b- ik bitje egyenlő 1-vel, és hamis egyébként. Hasonlóképpen jelöljük s j- t is tételként, igaz, ha s j- edik bitje 1, és hamis egyébként. Más javaslatokat is bemutatunk:

• r j akkor igaz, ha a j- edik bitnek van hordozhatósága , egyébként hamis;
• g j igaz, ha a j- edik bitnél hordozást generálunk , egyébként hamis;
• p j igaz, ha a lehetséges hordozást a j- edik bitre terjesztik, egyébként hamis.

Nekünk van :

• g j = a j ∧ b j
• p j = a j ∨ b j
• r j = (g 0 ∧ p 1 ∧ ... ∧ p j-1 ) ∨ (g 1 ∧ p 2 ∧ ... ∧ p j-1 ) ∨ ... ∨ g j-1
• s j = (a j ⊕ b j ⊕ r j ) ∨ (a j ∧ b j ∧ r j ), ha j ≤ n
• s n + 1 = r n + 1

Az áramkörben a fenti képleteknek megfelelő kapuk száma polinom n-ben. Ezenkívül az áramkör mélysége állandó, amint azt a fenti ábrán látható áramkör mutatja.

 

Ugyanígy a kivonás AC 0-ban van .

Példák nem AC 0 problémákra

Paritás

A paritásfüggvény olyan predikátum, amely 1-et ad vissza, ha a bemenetben az 1 bitek száma páros, és amely egyébként 0-t ad vissza. Az 1970-es években , nem volt ismert, ha voltak AC 0 áramkörök számára a klikk probléma vagy utazó ügynök probléma . Valójában Furst, Saxe és Sipser , valamint függetlenül Ajtai Miklós megmutatta, hogy ez nem így van. Még azt is kimutatták, hogy egy sokkal egyszerűbb állítmány, nevezetesen a paritásfüggvény nem tartozik az AC 0-ba . Johan Håstad ezután erősebb eredményt mutatott, a váltó lemmát  (in) . Mivel a paritás funkció az NC 1 , vezetjük le, hogy a felvétel AC 0 az NC 1 szigorú.

Többség

A többségi függvény n bitet vesz bemenetként, és 1-et ad vissza, ha a bitek szigorúan több mint a fele egyenlő 1-vel. Ez a függvény nincs AC 0-ban . Mi lehet ennek igazolására abszurd, ha többség van AC 0 hozzáadásával további biteket, tudjuk tesztelni, ha x ≥ k , ahol x az egész bitjei által a szóban forgó k egy konstans; onnan tesztelhetjük, hogy x = k  ; és ezért tesztelje a paritást , miközben AC 0-ban van , ami ellentmondás.

Szorzás

A szorzás nincs AC 0-ban, és a paritásfüggvény redukciója mutatja. Másrészt az NC 1-ben van .

Primalitás

Az az elsődleges predikátum, amely teszteli, hogy egy egész szám prím- e, nincs AC 0-ban .

Leíró összetettség

Class AC 0 kapcsolódik elsőrendű logikában a leíró összetettségét .

Megjegyzések és hivatkozások

1. (en) Sanjeev Arora és Boaz Barak , Számítási komplexitás: modern megközelítés , Cambridge University Press ,2009( ISBN  0-521-42426-7 ) , fej .  14. („Az áramkör alsó határai”) , p.  248
2. Sylvain Perifel , algoritmikus összetettség , ellipszis ,2014, 432  p. ( ISBN  9782729886929 , online olvasás ) , fejezet.  5. cikk ("Egységesség és nem egységesség")
3. (in) "  Tanfolyam Arnsfelt Kristoffer Hansen AC  " a helyszínen Arnsfelt Kristoffer Hansen az Aarhusi Egyetemen (Dannemark) , p.  2
4. Merrick Furst , James B. Saxe és Michael Sipser , „  Paritás, áramkörök és a polinom-idő hierarchia  ”, Math. Syst. Elmélet , vol.  17,1984, P.  13–27 ( ISSN  0025-5661 , DOI  10.1007 / bf01744431 , zbMATH  0534.94008 )
5. Ajtai Miklós , „  ∑ 1 1-képlet a véges szerkezetekről  ”, Annals of pure and alkalmazott logic , vol.  24, n o  1,1983, P.  1-48
6. Johan Håstad , „Majdnem optimális alsó határok kis mélységű áramkörökhöz” , a 18. éves {ACM} szimpóziumon a számítástechnika elméletéről, 1986. május 28–30., Berkeley, Kalifornia, {USA} ,1986( DOI  10.1145 / 12130.12132 ) , p.  6-20
7. (in) "  3. olvasás: AC0, a kapcsolási lemma  "
8. (a) "  Az olvasás 5 AC0 és TC0  "
9. Eric Allender , Michael Saks és Igor Shparlinski , „  A Bound for Primality  ”, Journal of Computer and System Sciences , vol.  62,1 st március 2001, P.  356-366 ( DOI  10.1006 / jcss.2000.1725 , online olvasás , hozzáférés : 2016. június 28. )
10. (a) Neil Immerman , Leíró komplexitás , New York, Springer-Verlag ,1999, 268  p. ( ISBN  0-387-98600-6 , online előadás ).

Külső hivatkozás

• en) AC 0 osztály a Komplexitás Állatkertben