الصفوف العدّية المعرّفة وفق مجموعة الأعداد الأولية


الملخص بالعربية

تعتبر مسألة P-NP أهم مسألة في نظرية الحوسبة و التعقيد الحسابي و من خلال دراستها تم تعريف و دراسة صفوف تعقيد أخرى مثل coNP ،PP، ..في هذا البحث تمّ تعريف صفوف تعقيد جديدة لحاسبة تورينك اللاحتمية بزمن كثيرة حدود، اعتمادا على مجموعة الأعداد الأولية و الأعداد المركبة لـ k- عدد أولي .

المراجع المستخدمة

GUNDERMANN T.; NASSER N. A., WECHSUNG G.; "A survey on counting classes"; In Proceedings, Fifth Annual Structure in Complexity Theory Conference, pages 140-153, Barcelona, Spain, 8-11 July 1990. IEEE Computer Society Press
COOK S. A. "The complexity of theorem-proving procedures", in Proceedings of the third annual ACM symposium on Theory of computing, STOC ’71, ACM, New York, NY, USA, 1971, pp. 151–158
BERMAN L., HARTMANIS J., "On isomorphism and density of NP and other complete sets", SIAMJC6(1977), 305-322

تحميل البحث