AC0

حساب البت رقم i في مجموع رقمين a و b في AC⁰. الصورة توضح دائرة عديد حدود حجمها من حجم الدخل (2n). وعمق ثابت (في هذه الحالة 5).

في علم التعقيد الحسابي AC⁰ هو قسم كل المسائل التي يمكن أن تُحل بواسطة دوائر بوليانية عمقها(depth) ثابت وحجمها(size) كثير حدود وعدد اطراف الدخل(fan-in) غير محدود (بما أن الحجم محدود بواسطة كثير حدود فإن عدد اطراف الدخل محدود ليكون كذلك كثير حدود) , هذا القسم هو الاصغر في هرم AC ويحوي القسم NC⁰ وهو قسم له نفس التعريف إلا أن عدد اطراف الدخل(fan-in) محدود .

في 1984 فورست ,ساكس وسبسر برهنوا أن حساب الزوجية لعدد مُعطى ليس تابعا للقسم $AC^{0}$ حتى عندما لا تكون الدوائر موحدة (nonuniform) , وبهذا فانه تبين أنَّ $AC^{0}\subsetneq NC^{1}$ بمساعدة هذه النظرية نستنج أنه يوجد أوركل (مُوحي) الذي يفصل بيسبايس عن أس هيدروجيني أي انه PH≠PSPACE حسب هذا الاوراكل .

عمليات الحساب مثل الجمع والطرح تابعة لهذا القسم اما الضرب فلا يتبع .

انظر أيضا

• قسم تعقيد
• نظرية التعقيد الحسابي.
• مسألة P=NP
• خوارزمية