نظرية التعقيد الحسابي
من ويكيبيديا، الموسوعة encyclopedia
نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسام التعقيد complexity classes ببعضها، والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها.[1][2][3]
صنف فرعي من | |
---|---|
جزء من | |
المواضيع |
تحتاج هذه المقالة كاملةً أو أجزاءً منها إلى تدقيق لغوي أو نحوي. (يونيو 2018) |
ويمكن اعتبارها مسألة صعبة إذا استخدمت كمية مُعينة من الموارد أياً كانت الخوارزمية. ولعل النماذج الحسابية هي الطريقة الأمثل في هذه النظرية لدراسة هذه المسائل وتحديد كمية الموارد اللازمة مثل: الوقت أو حجم المكان الإضافي اللازم، وتوجد معايير تعقيد أخرى مثل: الاتصال (مستخدم في نظرية تعقيد الاتصال) وعدد البوابات في الدارات المنطقية (مستخدم في نظرية تعقيد الدارات المنطقية) وكذلك عدد المعالجات (مستخدم في الحساب المتوازي).
وأحد أهم أساسيات نظرية التعقيد الحسابي هي إظهار الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به.
المجالات القريبة في علم الحاسوب النظري هي تحليل الخوارزميات ونظرية الحاسوبية، والفرق بين تحليل الخوارزميات ونظرية التعقيد الحسابية هو أن الأول يسأل عن خوارزمية معينة لحل مسألة، بينما الآخر يسأل عن كل الخوارزميات التي يمكنها حل المسألة، وبالتحديد فإن الأخير يحاول تصنيف المسائل التي يمكن حلها أو عدم حلها بوضع كمية مُحددة من الموارد، أما وضع الحدود للموارد الموجودة هو ما يميز نظرية التعقيد الحسابي عن النظرية الحاسوبية أي أن النظرية الحاسوبية تسأل عن أية مسائل يمكن حلها بواسطة خوارزمية.