AC 0

تُعدّ AC ⁰ (الدائرة المتناوبة) فئة تعقيد تُستخدم في حساب تعقيد الدوائر . وهي أصغر فئة في التسلسل الهرمي لـ AC ، وتتألف من جميع عائلات الدوائر ذات العمق O(1) والحجم متعدد الحدود، مع عدد غير محدود من بوابات AND و OR (نسمح ببوابات NOT فقط عند المدخلات). ^{[ 1 ]} وبالتالي، فهي تحتوي على NC ⁰ ، التي تحتوي فقط على عدد محدود من بوابات AND و OR. ^{[ 1 ]} تُسمى هذه الدوائر "دوائر متناوبة"، لأنه يكفي أن تتناوب الطبقات بين استخدام جميع بوابات AND وجميع بوابات OR، حيث أن استخدام بوابة AND واحدة تلو الأخرى يُكافئ استخدام بوابة AND واحدة، وينطبق الأمر نفسه على بوابات OR.

يمكن حساب جمع وطرح الأعداد الصحيحة في AC ⁰ ، ^{[ 2 ]} ولكن الضرب ليس كذلك (على وجه التحديد، عندما تكون المدخلات عددين صحيحين تحت التمثيل الثنائي المعتاد ^{[ 3 ]} أو التمثيل ذي الأساس 10 للأعداد الصحيحة).

بما أنها فئة دوائر، مثل P/poly ، فإن AC ⁰ تحتوي أيضًا على كل لغة أحادية .

من وجهة نظر التعقيد الوصفي ، فإن DLOGTIME - uniform AC ⁰ يساوي الفئة الوصفية FO +BIT لجميع اللغات التي يمكن وصفها في منطق الرتبة الأولى مع إضافة مسند BIT ، أو بدلاً من ذلك بواسطة FO(+, ×)، أو بواسطة آلة تورينج في التسلسل الهرمي اللوغاريتمي . ^{[ 4 ]}

في عام 1984، أظهر كل من فورست وساكس وسيبسر أن حساب تكافؤ بتات الإدخال (على عكس مسائل الجمع/الطرح المذكورة أعلاه والتي كانت تحتوي على مدخلين) لا يمكن تحديده بواسطة أي دوائر AC ⁰ ، حتى مع عدم التجانس. وبالمثل، فإن حساب الأغلبية ليس كذلك أيضًا.${\displaystyle {\mathsf {AC}}^{0}}$[ ^{5 ] [ 1 ]} يترتب على ذلك أن AC ⁰ أصغر تمامًا من TC ^{0. لاحظ أن "PARITY "} يُطلق عليه أيضًا " XOR " في المراجع.

ومع ذلك، فإن التكافؤ بالكاد يخرج عن AC ⁰ ، بمعنى أنه لأي${\displaystyle k>0}$توجد عائلة من الدوائر المتناوبة التي تستخدم العمق${\displaystyle \lceil k\ln n/\ln \ln n\rceil }$والحجم${\displaystyle O\left(2^{(\ln n)^{1/k}}{\frac {n}{(\ln n)^{1/k}}}\right)}$[ ^{6 ] : 135 على وجه الخصوص} ، تحديد${\displaystyle k}$إذا كان ثابتًا كبيرًا، فإنه توجد عائلة من الدوائر المتناوبة التي تستخدم العمق${\displaystyle O(\ln n/\ln \ln n)\ll O(\ln n)}$والحجم أكبر قليلاً من الخط المستقيم.

${\displaystyle {\mathsf {AC}}^{0}}$يمكن تقسيمها بشكل أكبر إلى تسلسل هرمي للغات التي تتطلب طبقة واحدة، أو طبقتين، وما إلى ذلك.${\displaystyle {\mathsf {AC}}_{d}^{0}}$ليكن فئة اللغات القابلة للتقرير بواسطة عائلة دوائر عتبة تصل إلى عمق${\displaystyle d}$:$${\displaystyle {\mathsf {AC}}_{1}^{0}\subset {\mathsf {AC}}_{2}^{0}\subset \cdots \subset {\mathsf {AC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {AC}}_{d}^{0}}$$المشكلة التالية هي${\displaystyle {\mathsf {AC}}_{d}^{0}}$- مكتملة في ظل شرط التوحيد: بالنظر إلى رسم بياني شبكي بطول وعرض متعدد الحدود${\displaystyle d}$، تحديد ما إذا كان رأسان معينان متصلين. ^{[ 7 ]}

إضافة اثنين${\displaystyle n}$الأعداد الصحيحة ذات البتات هي${\displaystyle {\mathsf {AC}}_{3}^{0}}$لكن ليس في${\displaystyle {\mathsf {AC}}_{2}^{0}}$[ ^{6 ] : 148​}