مشكلة دالة

في نظرية التعقيد الحسابي ، تُعرَّف مسألة الدالة بأنها مسألة حسابية يُتوقع فيها مخرج واحد لكل مُدخل، لكن هذا المخرج يكون أكثر تعقيدًا من مخرج مسألة القرار . ففي مسائل الدوال، لا يكون المخرج ببساطة "نعم" أو "لا".

مسألة دالة${\displaystyle P}$يتم تعريفها من خلال علاقة${\displaystyle R}$على سلاسل من أبجدية عشوائية${\displaystyle \Sigma }$:

${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}.}$

لاحظ أن${\displaystyle R}$لا يشترط أن تكون علاقة ثنائية وظيفية .

تقوم خوارزمية بحل${\displaystyle P}$إذا كان لكل مدخل${\displaystyle x}$بحيث يوجد${\displaystyle y}$مُرضٍ${\displaystyle (x,y)\in R}$، ينتج الخوارزمية واحدة من هذه${\displaystyle y}$وإذا لم يكن هناك مثل هذا${\displaystyle y}$يرفضها.

تسمح مشكلة دالة الوعد للخوارزمية بفعل أي شيء (وبالتالي قد لا تنتهي) إذا لم يكن هناك مثل هذا${\displaystyle y}$موجود.

تُعرف مسألة إرضاء الدوال المنطقية، أو اختصارًا FSAT ، بأنها مسألة دالة معروفة. ويمكن صياغة هذه المسألة، المرتبطة ارتباطًا وثيقًا بمسألة اتخاذ القرار SAT ، على النحو التالي:

بالنظر إلى صيغة اقتراحية${\displaystyle \varphi }$مع المتغيرات${\displaystyle x_{1},\ldots ,x_{n}}$ابحث عن مهمة${\displaystyle x_{i}\rightarrow \{{\text{TRUE}},{\text{FALSE}}\}}$بحيث${\displaystyle \varphi }$يُقيّم إلى${\displaystyle {\text{TRUE}}}$أو يقررون أنه لا يوجد مثل هذا التكليف.

في هذه الحالة العلاقة${\displaystyle R}$يتم تحديدها بواسطة أزواج من الصيغ المنطقية المشفرة بشكل مناسب والتعيينات المُرضية. بينما يتم تغذية خوارزمية SAT بصيغة${\displaystyle \varphi }$، يحتاج فقط إلى إرجاع "غير قابل للإرضاء" أو "قابل للإرضاء"، تحتاج خوارزمية FSAT إلى إرجاع تعيين مُرضٍ في الحالة الأخيرة.

ومن الأمثلة البارزة الأخرى مسألة البائع المتجول ، التي تطلب المسار الذي سلكه البائع، ومسألة تحليل الأعداد الصحيحة إلى عواملها الأولية ، التي تطلب قائمة العوامل.

لنفترض مشكلة قرار عشوائية${\displaystyle L}$في فئة NP . بحسب تعريف NP ، يوجد نظام من الشهادات بحيث يكون لكل حالة من حالات المشكلة${\displaystyle x}$أي أن الإجابة بـ "نعم" تعني أن الشهادة ذات حجم متعدد الحدود${\displaystyle y}$وهذا بمثابة دليل على إجابة "نعم" (أما حالات المشكلة التي تمت الإجابة عليها بـ "لا" فلا يوجد لها مثل هذه الشهادات). وبالتالي، فإن مجموعة هذه الأزواج${\displaystyle (x,y)}$يشكل علاقة، تمثل مسألة الدالة "المعطاة"${\displaystyle x}$في${\displaystyle L}$ابحث عن شهادة${\displaystyle y}$ل${\displaystyle x}$تُسمى مسألة الدالة هذه بصيغة دالة من${\displaystyle L}$; ينتمي إلى فئة FNP .

وعلى العكس من ذلك، فإن كل مشكلة R في FNP تؤدي إلى مشكلة قرار (فريدة) مقابلة: بالنظر إلى x ، قرر ما إذا كان هناك y بحيث يتحقق R ( x , y ).

يمكن اعتبار فئة FNP نظيرًا لفئة NP في مجال الدوال ، حيث يمكن التحقق من حلول مسائل FNP بكفاءة (أي في وقت متعدد الحدود بالنسبة لطول المدخلات) ، ولكن ليس بالضرورة إيجادها بكفاءة . في المقابل، تتكون فئة FP ، التي يمكن اعتبارها نظيرًا لفئة P في مجال الدوال ، من مسائل دوال يمكن إيجاد حلولها في وقت متعدد الحدود.

لاحظ أن مشكلة FSAT المذكورة أعلاه يمكن حلها باستخدام عدد قليل من الاستدعاءات لروتين فرعي يحدد مشكلة SAT : يمكن للخوارزمية أولاً أن تسأل عما إذا كانت الصيغة${\displaystyle \varphi }$قابلة للتحقيق. بعد ذلك، يمكن للخوارزمية تثبيت المتغير${\displaystyle x_{1}}$قم بتعيين القيمة إلى TRUE ثم اسأل مرة أخرى. إذا كانت الصيغة الناتجة لا تزال قابلة للتحقيق، فإن الخوارزمية تستمر.${\displaystyle x_{1}}$تم إصلاحها إلى القيمة TRUE وتستمر في الإصلاح${\displaystyle x_{2}}$وإلا فإنه يقرر ذلك${\displaystyle x_{1}}$يجب أن تكون النتيجة خاطئة وتستمر. بالتالي، يمكن حل مسألة FSAT في وقت متعدد الحدود باستخدام وسيط لتحديد مسألة SAT . بشكل عام، تُسمى المسألة في FNP قابلة للاختزال الذاتي إذا أمكن حلها في وقت متعدد الحدود باستخدام وسيط لمسألة القرار المُستنتجة منها. كل صيغة دالة لكل مسألة NP-كاملة قابلة للاختزال الذاتي. توجد عدة مفاهيم (مختلفة قليلاً) للاختزال الذاتي. ^{[ 1 ] [ 2 ] [ 3 ]}

يمكن تبسيط مسائل الدوال بشكل مشابه لمسائل القرار: مسائل الدوال المعطاة${\displaystyle R}$و${\displaystyle S}$نقول ذلك${\displaystyle R}$يتقلص إلى${\displaystyle S}$إذا كانت هناك دوال قابلة للحساب في زمن متعدد الحدود${\displaystyle f}$و${\displaystyle g}$بحيث يكون ذلك في جميع الحالات${\displaystyle x}$ل${\displaystyle R}$والحلول الممكنة${\displaystyle y}$ل${\displaystyle S}$ويرى ذلك أن

• لو${\displaystyle x}$لديه${\displaystyle R}$الحل، إذن${\displaystyle f(x)}$لديه${\displaystyle S}$-حل.
• ${\displaystyle (f(x),y)\in S\implies (x,g(x,y))\in R.}$

وبالتالي، من الممكن تعريف مسائل FNP-hard بشكل مشابه لمسائل NP-hard:

مشكلة${\displaystyle R}$تُعتبر مسألة FNP-صعبة إذا أمكن اختزال كل مشكلة في FNP إلى${\displaystyle R}$مشكلة${\displaystyle R}$تُعتبر المسألة FNP-كاملة إذا كانت FNP-صعبة وتقع ضمن FNP . تُعتبر المسألة FSAT مسألة FNP-كاملة، وبالتالي، من خلال خاصية الاختزال الذاتي لـ FSAT، يتحقق ما يلي:${\displaystyle \mathbf {P} =\mathbf {NP} }$إذا وفقط إذا${\displaystyle \mathbf {FP} =\mathbf {FNP} }$.

العلاقة${\displaystyle R(x,y)}$يُستخدم هذا الأسلوب لتعريف مسائل الدوال، ولكنه يعيبه أنه قد يكون غير مكتمل: فليس كل مدخل${\displaystyle x}$بالضرورة له نظير${\displaystyle y}$بحيث${\displaystyle (x,y)\in R}$لذا، فإن مسألة إمكانية حساب المخرجات لا تنفصل عن مسألة وجودها. وللتغلب على هذه المشكلة، من المفيد النظر في حصر مسائل الدوال على العلاقات الكلية، مما ينتج عنه فئة TFNP كفئة فرعية من FNP . تحتوي هذه الفئة على مسائل مثل حساب توازنات ناش البحتة في بعض الألعاب الاستراتيجية حيث يكون وجود حل مضمونًا. بالإضافة إلى ذلك، إذا احتوت TFNP على أي مسألة كاملة من فئة FNP، فإنه يترتب على ذلك أن${\displaystyle \mathbf {NP} ={\textbf {co-NP}}}$.

• مشكلة اتخاذ القرار
• مشاكل البحث
• مسألة العد (التعقيد)
• مشكلة التحسين