قسم تعقيد

من ويكيبيديا، الموسوعة الحرة

في علم التعقيد الحسابي، قسم تعقيد هي مجموعة من المسائل المُتعلقة بالاساس فيما بينها بمورد مُعين، اغلب الاقسام لديها التعريف التالي:

مجموعة المسائل التي يمكن حلها بواسطة موارد حيث أنَّ n هو طول المُدخل.

على سبيل المثال: القسم NP هو مجموعة المسائل التي يمكن حلها بوقت حدودي (أي ) بواسطة آلة تيورنج غير حتمية، مثال آخر هو القسم بيسبايس وهو مجموعة المسائل التي يمكن حلها بواسطة آلة تيورنج حتمية وتستخدم مكان اضافي طوله حدودي (أي انها تسخدم مكان اضافي).[1][2]

الاقسام الأساسية مُعرفة حسب المتغيرات التالية:

  1. نوع المسألة الحسابية: على الاغلب المسائل هي مسائل تقرير (decision problem), ولكن اقسام التعقيد يمكن تعريفها أيضا بواسطة مسائل دوال (function problem) مثل القسم FP أو مسائل عد (counting problem) مثل P# أو مسائل استمثال...
  2. نوع نموذج الحساب: على الاغلب نموذج الحساب هو آلة تيورنج الحتمية ولكن العديد من الاقسام تُعرف بالة تيورنج غير حتمية، دوائر بوليانية، آلة تيورنج كمومية...
  3. المورد الذي يتم تحديده والحدود: مثل «وقت حدودي», «مكان حدودي», «وقت لوجارثمي», ...

بعض الاقسام يمكن تشخيصها بواسطة المنطق الرياضي اللازم لتعريفها.

بعض أهم الاقسام[عدل]

يتم تعريف الاقسام وفقا لنوع المورد أو النموذج المُستخدم ونلحق هنا بعض أهم الاقسام المعروفة:

على الاغلب هنا أُستخدِم النموذج الحسابي: آلة تيورنج حتمية وغير حتمية.

اقسام أخرى مهمة من ضمنها: BPP , RP,ZPP وهذه الاقسام مُعرفة بواسطة آلة تيورنج احتمالية ; الاقسام AC,NC وهذه الاقسام مُعرفة بواسطة دوائر بوليانية ; BQP,QAM وهذه الاقسام مُعرفة بواسطة آلة تيورنج كمومية ; #P وهو قسم مسائل عد. اقسام مثل IP,AM مُعرفة بواسطة نظام براهين تفاعلي. ALL هو قسم كل المسائل.

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

استزادة[عدل]

مصادر[عدل]

  1. ^ "معلومات عن قسم تعقيد على موقع xlinux.nist.gov". xlinux.nist.gov. مؤرشف من الأصل في 2021-04-30.
  2. ^ "معلومات عن قسم تعقيد على موقع brilliant.org". brilliant.org. مؤرشف من الأصل في 2020-11-25.
  • Algorithms and Theory of Computation Handbook, Second Edition - 2 Volume Set (Chapman & Hall/CRC Applied Algorithms and Data Structures series), ISBN 1-58488-818-0