Egy nemuniform polinom méretû ACC hálózatcsalád Boole hálózatok egy olyan C_0, C_1, ... olyan sorozata, melyre minden i-re C_i-ben a konstans 0, konstans 1, és {x_1,...,x_i} input kapukat, tetszõleges befokú ÉS és VAGY kapukat, NEM kapukat és tetszõleges m-re MOD_m kapukat használhatjuk. Továbbá a hálózatcsalád polinom méretû és konstans mélységû: van olyan k,d>0 konstans, amire C_n mérete legfeljebb n^k, mélysége pedig legfeljebb d.
Hálózatcsaláddal {0,1} fölötti nyelveket tudunk eldönteni úgy, hogy u pont akkor van benne a nyelvben, ha a C_{|u|} hálózatot kiértékelve úgy, hogy az x_i címkéjû kapuknak u i-edik betûjét adjuk, a hálózat értéke 1 lesz.
A hálózatcsaládban a "nemuniform" jelzõ arra vonatkozik, hogy semmilyen megkötést nem teszünk arra, hogy n-bõl C_n kiszámítható-e valamilyen erõforráskorláton belül. (Így vannak olyan eldönthetetlen nyelvek is, melyek eldönthetõk ilyen hálózatcsaláddal...)
Rég ismert, hogy MOD_m kapuk nélkül (ezt hívják nemunifom AC^0-nak) pl. a paritásfüggvény nem számítható ki nemuniform polinom méretû hálózatcsaláddal. A többségi függvény sem. A mai napig nyitott kérdés viszont, hogy a többségi függvény kiszámítható-e nemuniform polinom méretû ACC hálózatcsaláddal; sõt, még a következõ kérdés is egészen a nagyonközelmúltig nyitott volt:
"Van-e olyan nyelv EXP^NP-ben, amit nem lehet eldönteni olyan nemuniform, 3 mélységû, polinom méretû ACC hálózatcsaláddal, amiben csak MOD_6 kaput használunk?"
Úgy néz ki, hogy ezt a kérdést negatívan válaszolta meg Ryan Williams hétfõn, mikor is bebizonyította, hogy NTIME[2^n]-ben is van nemuniform polinom méretû ACC családdal NEM eldönthetõ nyelv. Errõl a bizonyításról beszélnék.
Lipton messzi vázlata és magára a papírra egy link itt: http://rjlipton.wordpress.com/2010/11/08/a-breakthrough-result/
Minden érdeklõdõt szeretettel várunk,
Péter