مشكلة حسابية

في علم الحاسوب النظري ، تُعرَّف المشكلة بأنها مشكلة تتطلب حلاً باستخدام خوارزمية . على سبيل المثال، مشكلة التحليل إلى عوامل.

"إذا كان لدينا عدد صحيح موجب n ، فأوجد عاملًا أوليًا غير تافه للعدد n ."

تُعدّ مسألة التحليل إلى عوامل أولية مسألة حسابية لها حل، إذ توجد العديد من خوارزميات التحليل المعروفة . يمكن النظر إلى المسألة الحسابية على أنها مجموعة من الحالات ، بالإضافة إلى مجموعة حلول ، قد تكون فارغة، لكل حالة. السؤال المطروح هو: هل توجد خوارزمية تربط الحالات بالحلول؟ على سبيل المثال، في مسألة التحليل إلى عوامل أولية ، تكون الحالات هي الأعداد الصحيحة n ، والحلول هي الأعداد الأولية p التي تُمثّل العوامل الأولية غير التافهة للعدد n . من الأمثلة على المسائل الحسابية التي ليس لها حل مسألة التوقف . تُعدّ المسائل الحسابية من أهم مجالات الدراسة في علوم الحاسوب النظرية.

غالبًا ما يهتم المرء ليس فقط بوجود خوارزمية ما، بل أيضًا بمدى كفاءتها. يتناول مجال نظرية التعقيد الحسابي هذه التساؤلات من خلال تحديد مقدار الموارد ( التعقيد الحسابي ) اللازمة لحل مشكلة معينة، وشرح سبب استحالة حل بعض المشكلات أو عدم إمكانية حسمها . تنتمي المشكلات الحسابية القابلة للحل إلى فئات التعقيد التي تُعرّف بشكل عام الموارد (مثل الوقت، والمساحة/الذاكرة، والطاقة، وعمق الدائرة) اللازمة لحسابها (حلها) باستخدام آلات مجردة متنوعة . على سبيل المثال، فئات التعقيد

• P ، مسائل تستهلك وقتًا متعدد الحدود للآلات الكلاسيكية الحتمية
• BPP ، وهي مسائل تستهلك وقتًا متعدد الحدود للآلات الكلاسيكية الاحتمالية (مثل أجهزة الكمبيوتر المزودة بمولدات أرقام عشوائية).
• BQP ، وهي مسائل تستهلك وقتًا متعدد الحدود للآلات الكمومية الاحتمالية.

تُمثَّل كلٌّ من الحالات والحلول بسلاسل ثنائية ، أي عناصر المجموعة {0، 1} ^* . ^{[ أ ]} على سبيل المثال، تُمثَّل الأعداد الطبيعية عادةً بسلاسل ثنائية باستخدام الترميز الثنائي . وهذا مهم لأن التعقيد يُعبَّر عنه كدالة لطول تمثيل المدخلات.

في نظرية التعقيد الحسابي ، يُفترض ضمنيًا عادةً أن أي سلسلة نصية في المجموعة {0، 1} ^تمثل حالة من حالات المسألة الحسابية المطروحة. مع ذلك، في بعض الأحيان لا تمثل جميع السلاسل النصية في المجموعة {0، 1} ^حالات صالحة، ويتم تحديد مجموعة فرعية مناسبة من المجموعة {0، 1} ^{كمجموعة} "الحالات الصالحة". تُسمى المسائل الحسابية من هذا النوع مسائل الوعد .

فيما يلي مثال على مشكلة وعد (قرار):

"بالنظر إلى الرسم البياني G ، حدد ما إذا كان حجم كل مجموعة مستقلة في G لا يتجاوز 5، أو ما إذا كان G يحتوي على مجموعة مستقلة بحجم 10 على الأقل."

هنا، الحالات الصالحة هي تلك الرسوم البيانية التي يكون حجم مجموعتها المستقلة القصوى إما 5 على الأكثر أو 10 على الأقل.

تُصاغ مسائل وعد القرار عادةً على شكل أزواج من المجموعات الجزئية المنفصلة ( L _yes , L _no ) من المجموعة {0, 1} ^* . الحالات الصالحة هي تلك الموجودة في L _yes ∪ L _no . تمثل L _yes و L _no الحالات التي تكون إجابتها نعم ولا ، على التوالي.

تلعب مشاكل الوعود دورًا مهمًا في العديد من مجالات التعقيد الحسابي ، بما في ذلك صعوبة التقريب ، واختبار الخصائص ، وأنظمة الإثبات التفاعلية .

• الحوسبة الجانبية ، مناهج بديلة لحل المشكلات حسابيًا
• نموذج الحوسبة
• مشكلة الحوسبة العابرة

• إيفن، شيمون ؛ سيلمان، آلان ل .؛ يعقوبي، يعقوب (1984)، "تعقيد مسائل الوعد مع تطبيقات على التشفير بالمفتاح العام"، المعلومات والتحكم ، 61 (2): 159-173 ، doi : 10.1016/S0019-9958(84)80056-X.
• جولدرايش، أوديد (2008)، التعقيد الحسابي: منظور مفاهيمي ، مطبعة جامعة كامبريدج ، رقم ISBN 978-0-521-88473-0.
• جولدرايش، أوديد ؛ ويجدرسون، آفي (2008)، "IV.20 التعقيد الحسابي"، في جوورز، تيموثي ؛ بارو-جرين، جون؛ ليدر، إيمري (محررون)، دليل برينستون للرياضيات ، مطبعة جامعة برينستون، الصفحات 575-604 ، ISBN  978-0-691-11880-2.