قسم تعقيد

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

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

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

على سبيل المثال : القسم NP هو مجموعة المسائل التي يمكن حلها بوقت حدودي ( اي ) بواسطة الة تيورنج غير حتمية, مثال اخر هو القسم بيسبايس وهو مجموعة المسائل التي يمكن حلها بواسطة الة تيورنج حتمية وتستخدم مكان اضافي طوله حدودي ( اي انها تسخدم مكان اضافي) .

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

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

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

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

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

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

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

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

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

مصادر[عدل]

  • 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