عبد العزيز: بوت: إصلاح التحويلات

2022-12-14T03:53:08Z

بوت: إصلاح التحويلات

صفحة جديدة

في علم التعقيد الحسابي، '''قسم تعقيد''' هي مجموعة من المسائل المُتعلقة بالاساس فيما بينها بمورد مُعين، اغلب الاقسام لديها التعريف التالي:
: مجموعة المسائل التي يمكن حلها بواسطة <math> O(f(n))</math> موارد حيث أنَّ n هو طول المُدخل.

على سبيل المثال: القسم [[كثير حدود غير قطعي|NP]] هو مجموعة المسائل التي يمكن حلها بوقت حدودي (أي <math> O(n^c) </math>) بواسطة آلة تيورنج غير حتمية، مثال آخر هو القسم [[بيسبايس]] وهو مجموعة المسائل التي يمكن حلها بواسطة آلة تيورنج حتمية وتستخدم مكان اضافي طوله حدودي (أي انها تسخدم <math>O(n^c)</math> مكان اضافي).<ref>{{استشهاد ويب| مسار = https://xlinux.nist.gov/dads/HTML/complexityClass.html | عنوان = معلومات عن قسم تعقيد على موقع xlinux.nist.gov | ناشر = xlinux.nist.gov| مسار أرشيف = https://web.archive.org/web/20210430073914/https://xlinux.nist.gov/dads/HTML/complexityClass.html | تاريخ أرشيف = 30 أبريل 2021 }}</ref><ref>{{استشهاد ويب| مسار = https://brilliant.org/wiki/complexity-classes/ | عنوان = معلومات عن قسم تعقيد على موقع brilliant.org | ناشر = brilliant.org|مسار أرشيف= https://web.archive.org/web/20201125030715/https://brilliant.org/wiki/complexity-classes/|تاريخ أرشيف=2020-11-25}}</ref>

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

بعض الاقسام يمكن تشخيصها بواسطة المنطق الرياضي اللازم لتعريفها.
== بعض أهم الاقسام ==
يتم تعريف الاقسام وفقا لنوع المورد أو النموذج المُستخدم ونلحق هنا بعض أهم الاقسام المعروفة:
* <math> \mbox{L}=\mbox{DSPACE}[\mbox{log}(n)] </math>
* <math> \mbox{NL}=\mbox{NSPACE}[\mbox{log}(n)] </math>
* <math> \mbox{P}= \cup _ {k \ge 1} \mbox{DTIME}[n^k]</math>
* <math> \mbox{NP}= \cup _ {k \ge 1} \mbox{NTIME}[n^k]</math>
* <math> \mbox{PSPACE}= \cup _ {k \ge 1} \mbox{DSPACE}[n^k]</math>
* <math> \mbox{NPSPACE}= \cup _ {k \ge 1} \mbox{NSPACE}[n^k]</math>
* <math> \mbox{E}= \cup _ {k \ge 1} \mbox{DSPACE}[k^n]</math>
* <math> \mbox{NE}= \cup _ {k \ge 1} \mbox{NSPACE}[k^n]</math>
* <math> \mbox{EXP}= \cup _ {k \ge 1} \mbox{DSPACE}[2^{n^k}]</math>
* <math> \mbox{NEXP}= \cup _ {k \ge 1} \mbox{NSPACE}[2^{n^k}]</math>
* <math> \mbox{EXPSPACE}= \cup _ {k \ge 1} \mbox{DSPACE}[2^{n^k}]</math>
* <math> \mbox{NEXPSPACE}= \cup _ {k \ge 1} \mbox{NSPACE}[2^{n^k}]</math>

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

اقسام أخرى مهمة من ضمنها: [[BPP]] , RP,ZPP وهذه الاقسام مُعرفة بواسطة آلة تيورنج احتمالية ; الاقسام AC,NC وهذه الاقسام مُعرفة بواسطة دوائر بوليانية ; BQP,QAM وهذه الاقسام مُعرفة بواسطة آلة تيورنج كمومية ; #P وهو قسم مسائل عد. اقسام مثل IP,AM مُعرفة بواسطة نظام براهين تفاعلي. ALL هو قسم كل المسائل.
== انظر أيضًا ==
* [[نظرية التعقيد الحسابي]].
* [[مسألة كثير حدود وكثير حدود غير قطعي|مسألة P=NP]]
* [[خوارزمية]]
== استزادة ==
* [https://complexityzoo.uwaterloo.ca/Complexity_Zoo The Complexity Zoo]: قائمة كبيرة لكل الاقسام المعروفة.
== مصادر ==
{{مراجع}}

<div dir="LTR">
* 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
</div>
{{أقسام تعقيد}}
{{شريط بوابات|رياضيات|علم الحاسوب}}

[[تصنيف:أقسام التعقيد الحسابي]]
[[تصنيف:معلوماتية نظرية]]
[[تصنيف:نظرية التعقيد الحسابي]]

قسم تعقيد - تاريخ المراجعة

عبد العزيز: بوت: إصلاح التحويلات