AC ⁰ -AC⁰

AC ⁰ devresinin şeması : n giriş biti alttadır ve üst geçit çıkışı üretir; devre, her birinde polinom fanının VE- ve VEYA-geçitlerinden oluşur ve değişim derinliği bir sabit ile sınırlandırılır.

AC ⁰ , devre karmaşıklığında kullanılan bir karmaşıklık sınıfıdır . AC hiyerarşisindeki en küçük sınıftır ve sınırsız fanin AND kapıları ve OR kapıları ile O(1) derinliği ve polinom boyutundaki tüm devre ailelerinden oluşur . ( Yalnızca girişlerde DEĞİL kapılarına izin veriyoruz ). Bu nedenle , yalnızca sınırlı-fanin AND ve OR geçitlerine sahip olan NC ^0'ı içerir .

Örnek problemler

Tamsayı toplama ve çıkarma AC ^0'da hesaplanabilir , ancak çarpma değildir (en azından, tamsayıların olağan ikili veya taban-10 temsilleri altında değil).

P/poly gibi bir devre sınıfı olduğu için AC ⁰ da her birli dili içerir .

tanımlayıcı karmaşıklık

Bir kaynaktan açıklayıcı karmaşıklık açısından, DLOGTIME - düzgün AC ⁰ açıklayıcı sınıf eşittir FO tüm + BIT dilleri ilavesi ile birinci dereceden mantığı nitelendirilebilecek BIT yüklem , ya da seçenek olarak FO (+, x) ya da tarafından göre Turing makine içinde logaritmik hiyerarşi .

ayrılıklar

1984'te Furst, Saxe ve Sipser , bir girişin paritesinin hesaplanmasına, düzensizlik olsa bile herhangi bir AC ⁰ devresi tarafından karar veremeyeceğini gösterdi . O AC izler ⁰ eşit değildir NC ¹ sonuncu sınıfta devrelerin bir aile paritesi hesaplayabilir çünkü. Daha kesin sınırlar, lemmanın değiştirilmesinden sonra gelir . Bunları kullanarak, polinom hiyerarşisi ile PSPACE arasında bir oracle ayrımı olduğu gösterilmiştir .

Referanslar