AC (karmaşıklık)

In karmaşıklık teorisi , AC ise karmaşıklık sınıf birliği olarak tanımlanan AC i , AC i derinlik Boole devreleri tarafından karar sorunların karmaşıklığı sınıftır kapıları sınırsız gelen derecelik ANDs ve OO'lar vardır polinom boyutu, (in aslında, diğer kapılara "özel VEYA" veya DEĞİL kapıları olarak izin verilebilir, çünkü bunlar karmaşıklığı değiştirmeden AND'ler ve OR'ler tarafından ifade edilebilirler). ${\ displaystyle O (\ log ^ {i} n)}$

Özellikle AC 0 , polinom büyüklüğünde sabit derinlikli Boolean devreleri tarafından karar verilen problemlerin karmaşıklık sınıfıdır.

AC = NC

Sınıfları NC ve NC i AC, AC benzer olan I mantık kapıları Arity sınırlı olduğunu hariç. Sahibiz :

${\ displaystyle {\ mbox {NC}} ^ {i} \ alt küme {\ mbox {AC}} ^ {i} \ alt küme {\ mbox {NC}} ^ {i + 1}.}$

Böylece AC ve NC sınıfları eşittir.

Dış bağlantılar

(tr) Karmaşıklık Hayvanat Bahçesi'ndeki AC sınıfı