انتقل إلى المحتوى

AC0

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

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

في 1984 فورست ,ساكس وسبسر برهنوا أن حساب الزوجية لعدد مُعطى ليس تابعا للقسم حتى عندما لا تكون الدوائر موحدة (nonuniform) , وبهذا فانه تبين أنَّ بمساعدة هذه النظرية نستنج أنه يوجد أوركل (مُوحي) الذي يفصل بيسبايس عن أس هيدروجيني أي انه PH≠PSPACE حسب هذا الاوراكل .

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

انظر أيضا

[عدل]