قسم تعقيد

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

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

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

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

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

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

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

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

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

  •  \mbox{L}=\mbox{DSPACE}[\mbox{log}(n)]
  •  \mbox{NL}=\mbox{NSPACE}[\mbox{log}(n)]
  •  \mbox{P}= \cup _ {k \ge 1} \mbox{DTIME}[n^k]
  •  \mbox{NP}= \cup _ {k \ge 1} \mbox{NTIME}[n^k]
  •  \mbox{PSPACE}= \cup _ {k \ge 1} \mbox{DSPACE}[n^k]
  •  \mbox{NPSPACE}= \cup _ {k \ge 1} \mbox{NSPACE}[n^k]
  •  \mbox{E}= \cup _ {k \ge 1} \mbox{DSPACE}[k^n]
  •  \mbox{NE}= \cup _ {k \ge 1} \mbox{NSPACE}[k^n]
  •  \mbox{EXP}= \cup _ {k \ge 1} \mbox{DSPACE}[2^{n^k}]
  •  \mbox{NEXP}= \cup _ {k \ge 1} \mbox{NSPACE}[2^{n^k}]
  •  \mbox{EXPSPACE}= \cup _ {k \ge 1} \mbox{DSPACE}[2^{n^k}]
  •  \mbox{NEXPSPACE}= \cup _ {k \ge 1} \mbox{NSPACE}[2^{n^k}]

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

اقسام اخرى مهمة من ضمنها : 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