AC0

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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

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

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

انظر أيضا[عدل]