TFNP

• المدخلات : دالة قابلة للحساب متعدد الحدود f تقوم بتحويل مجموعة من n  +  1 عنصر إلى مجموعة من n عنصر.
• السؤال : أوجد عنصرين a و b بحيث يكون f ( a )  = f ( b ). 

ليكن x تطبيقًا، و y ثنائيًا من عناصر مجاله. العلاقة الثنائية في السؤال P ( x , y ) تعني "صورتا عنصري y تحت x متساويتان"، وبما أن التطبيق قابل للحساب في زمن متعدد الحدود، فإنه قابل للتقرير في زمن متعدد الحدود. علاوة على ذلك، يجب أن يوجد هذا الثنائي y لأي تطبيق بسبب مبدأ التوزيع .

فئة التعقيد${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$يمكن تعريفها بطريقتين مختلفتين، ولا يُعرف ما إذا كانت هاتان الطريقتان متكافئتين. إحدى الطريقتين تُطبّق F على نموذج الآلة لـ${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$من المعروف أنه وفقًا لهذا التعريف،${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$يتزامن مع TFNP. ^{[ 4 ]} ولرؤية ذلك، لاحظ أولاً أن التضمين${\displaystyle {\mathsf {TFNP}}\subseteq {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$يستنتج ذلك بسهولة من تعريفات الفئات. يمكن التحقق بسهولة من جميع الإجابات "نعم" على مسائل TFNP بحسب التعريف، وبما أن مسائل TFNP كلية، فلا توجد إجابات "لا"، لذا فمن البديهي أنه يمكن التحقق بسهولة من الإجابات "لا". بالنسبة للاحتواء العكسي، ليكن R علاقة ثنائية في${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$حلل R إلى${\displaystyle R_{1}\cup R_{2}}$بحيث${\displaystyle (x,0y)\in R_{1}}$متى بالضبط${\displaystyle (x,y)\in R}$و y هي إجابة "نعم" ، ولتكن R ₂ هي${\displaystyle (x,1y)}$مثل هذا ​${\displaystyle (x,y)\in R}$و y هي إجابة "لا". إذن العلاقةالثنائية${\displaystyle R_{1}\cup R_{2}}$يقع في TFNP.

يستخدم التعريف الآخر ذلك${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$من المعروف أن هذه فئة من مسائل القرار ذات سلوك جيد ، ويتم تطبيق F على هذه الفئة. وفقًا لهذا التعريف، إذا${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}={\mathsf {P}}}$ثم${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})={\mathsf {\color {Blue}FP}}}$.

تُعدّ فئة NP من أكثر فئات التعقيد دراسةً. ويُعتبر افتراض وجود مسائل غير قابلة للحل في NP مقبولًا على نطاق واسع، ويُستخدم غالبًا كأبسط فرضية لصعوبة المسائل. لذا، من الطبيعي التساؤل عن علاقة TFNP بفئة NP. من السهل ملاحظة أن حلول مسائل NP قد تُؤدي إلى حلول مسائل TFNP. مع ذلك، لا توجد مسائل TFNP معروفة بأنها NP-صعبة . ويعود هذا إلى كون مسائل TFNP مسائل كلية. لكي تكون مسألة ما NP-صعبة، يجب أن يكون هناك اختزال من مسألة NP-كاملة إلى المسألة محل الاهتمام. يتم الاختزال النموذجي من المسألة A إلى المسألة B عن طريق إنشاء وتحليل خريطة تُرسل حالات "نعم" من A إلى حالات "نعم" من B ، وحالات "لا" من A إلى حالات "لا" من B. لكن مسائل TFNP كلية، لذا لا توجد حالات "لا" لهذا النوع من الاختزال، مما يجعل تطبيق التقنيات الشائعة صعبًا. إلى جانب هذا الحدس العام، توجد عدة نتائج ملموسة تشير إلى أنه قد يكون من الصعب، بل من المستحيل، إثبات صعوبة مسائل TFNP من فئة NP. على سبيل المثال، إذا كانت أي مسألة TFNP كاملة من فئة NP، فإن NP = coNP، ^{[ 3 ]} وهو ما يُفترض عمومًا أنه غير صحيح، ولكنه لا يزال يمثل مشكلة مفتوحة رئيسية في نظرية التعقيد. يُعد هذا النقص في الصلة مع NP دافعًا رئيسيًا لدراسة TFNP كفئة مستقلة بذاتها.

PLS (اختصارًا لـ "البحث المحلي متعدد الحدود") هي فئة من المسائل المصممة لنمذجة عملية البحث عن الحل الأمثل المحلي لدالة ما. على وجه الخصوص، هي فئة مسائل الدوال الكلية التي يمكن اختزالها في وقت متعدد الحدود إلى المسألة التالية

بفرض وجود دائرتي إدخال S و C، تحتوي كل منهما على n بت إدخال و n بت إخراج، أوجد قيمة x بحيث ⁠${\displaystyle C(S(x))\leq C(X)}$⁠ .

يحتوي على الفئة CLS.

PPA (اختصارًا لـ "حجة التكافؤ في زمن متعدد الحدود") هي فئة من المسائل التي يضمن حلها مبرهنة المصافحة : أي رسم بياني غير موجه ذي رأس بدرجة فردية يجب أن يحتوي على رأس آخر بدرجة فردية . وتشمل هذه الفئة الفرعية PPAD . من بين المسائل الكاملة في PPA مسألة LONELY: بالنظر إلى دائرة تحدد مطابقة جزئية على ${\displaystyle \{0,1\}^{n}}$بحيث${\displaystyle {\vec {0}}}$إذا لم يكن هناك تطابق، فابحث عن رأس آخر غير متطابق. ^{[ 6 ]}

مبدأ PPP (اختصارًا لـ "مبدأ الحمام ذي الوقت متعدد الحدود") هو فئة من المسائل التي يضمن مبدأ الحمام حلها . وبشكل أدق، هو فئة من المسائل التي يمكن اختزالها في وقت متعدد الحدود إلى مسألة الحمام، والتي تُعرَّف على النحو التالي

بفرض وجود دائرة C ذات n بتات إدخال وإخراج، أوجد قيمة x بحيث${\displaystyle C(x)=0}$أو x ≠ y بحيث​​${\displaystyle C(x)=C(y)}$⁠ .

تتضمن فئة PPP الفئتين PPAD و PWPP. ومن أبرز المسائل في هذه الفئة مسألة حل الأعداد الصحيحة القصيرة . ^{[ 7 ]}

PPAD (اختصارًا لـ "حجة التكافؤ الموجهة في زمن متعدد الحدود") هو تقييد لـ PPA ليشمل المسائل التي تضمن حلولها نسخة موجهة من مبرهنة المصافحة . ويُعرَّف غالبًا بأنه مجموعة المسائل التي يمكن اختزالها في زمن متعدد الحدود إلى مسألة نهاية السطر.

بافتراض وجود دائرتين S و P مع n بتات إدخال وإخراج${\displaystyle S(0)\neq 0}$و​​${\displaystyle P(0)=0}$أوجد قيمة x بحيث​${\displaystyle P(S(x))\neq x}$أو​​${\displaystyle x\neq 0}$بحيث​​${\displaystyle S(P(x))\neq x}$⁠ .

يقع PPAD في تقاطع PPA و PPP، ويحتوي على CLS.

هنا، تُرسل الدائرة S في التعريف كل نقطة من الخط إلى النقطة التي تليها، أو إلى نفسها إذا كانت النقطة مصبًا. وبالمثل، تُرسل الدائرة P كل نقطة من الخط إلى النقطة التي تسبقها، أو إلى نفسها إذا كانت النقطة مصدرًا. تُحدد النقاط الواقعة خارج جميع الخطوط بتثبيتها تحت كل من P و S (بمعنى آخر، تُزال أي نقاط معزولة من الرسم البياني). ثم يتحقق الشرط ⁠${\displaystyle P(S(x))\neq x}$يُحدد هذا نهاية الخط، والتي إما أن تكون نقطة غرق أو تكون بحيث يكون S ( x ) = S ( y ) لنقطة أخرى y ؛ وبالمثل ، فإن الشرط${\displaystyle S(P(x))\neq x}$⁠ يحدد بداية الخط (بما أننا نفترض أن 0 هو مصدر، فإننا نشترط أن يكون الحل غير صفري في هذه الحالة).

البحث المحلي المستمر (CLS) هو فئة من مسائل البحث المصممة لنمذجة عملية إيجاد القيمة المثلى المحلية لدالة مستمرة على مجال مستمر. ويُعرَّف بأنه فئة المسائل التي يمكن اختزالها في وقت متعدد الحدود إلى مسألة النقطة المحلية المستمرة.

بالنظر إلى دالتين متصلتين من نوع Lipschitz، وهما S و C ، والمعاملين ε و λ ، أوجد نقطة ثابتة تقريبية من النوع ε للدالة S بالنسبة إلى C أو نقطتين تنتهكان استمرارية λ للدالة C أو S.

تم تعريف هذه الفئة لأول مرة بواسطة داسكالاكيس وباباديميتريو في عام 2011. ^{[ 8 ]} وهي تقع ضمن تقاطع PPAD وPLS، وقد ثبت في عام 2020 أن${\displaystyle {\mathsf {CLS}}={\mathsf {PPAD}}\cap {\mathsf {PLS}}}$[ ^{9 ] [ 10 ]} لقد تم تصميمها لتكون فئة من مسائل التحسين البسيطة نسبيًا والتي لا تزال تحتوي على العديد من المسائل المثيرة للاهتمام والتي يُعتقد أنها صعبة ^.

من الأمثلة على المسائل الكاملة لـ CLS إيجاد نقطة ε- KKT ، ^{[ 11 ]} وإيجاد نقطة ثابتة ε-Banach ^{[ 12 ]} ومسألة الانكماش المتري الفائق. ^{[ 13 ]}

تم تقديم EOPL وUEOPL (والتي تعني "نهاية خط الإمكانات" و"نهاية خط الإمكانات الفريدة") في عام 2020 بواسطة. ^{[ 11 ]}

تُغطي EOPL مسائل البحث التي يُمكن حلّها بالبحث المحلي، أي أنه من الممكن الانتقال من حل مُرشّح إلى آخر في وقت متعدد الحدود. يُمكن تفسير المسألة في EOPL على أنها رسم بياني مُوجّه وغير دوري ذو حجم أُسّي، حيث يُمثّل كل عقدة حلاً مُرشّحاً، وله تكلفة (تُسمى أيضاً الجهد) تزداد على طول الحواف. درجة الدخول والخروج لكل عقدة لا تتجاوز واحداً، مما يعني أن العقد تُشكّل مجموعة من الخطوط الطويلة أُسّياً. نهاية كل خط هي العقدة ذات التكلفة الأعلى على ذلك الخط. تحتوي EOPL على جميع المسائل التي يُمكن اختزالها في وقت متعدد الحدود إلى مسألة البحث End-of-Potential-Line.

بافتراض وجود دوائر إدخال S و P ، كل منهما تحتوي على n بتات إدخال و n بتات إخراج، و C تحتوي على n بتات إدخال و m بتات إخراج ،${\displaystyle S(0)\neq 0}$،​​${\displaystyle P(0)=0}$و​​${\displaystyle C(0)=0}$أوجد قيمة x بحيث

• يمثل x نهاية الخط${\displaystyle P(S(x))\neq x}$،​
• x هو بداية سطر ثانٍ${\displaystyle S(P(x))\neq x\neq 0}$أو​
• x ينتهك التكلفة المتزايدة${\displaystyle P(S(x))=x}$،​​${\displaystyle x\neq S(x)}$و​​${\displaystyle C(S(x))-C(x)\leq 0}$⁠

هنا، تُرسل النقطة S كل رأس من رؤوس الرسم البياني إلى الرأس الذي يليه، أو إلى نفسها إذا كان الرأس مُستقبِلًا. وبالمثل، تُرسل النقطة P كل رأس من رؤوس الرسم البياني إلى الرأس الذي يسبقها، أو إلى نفسها. تُحدَّد النقاط خارج الرسم البياني بتثبيتها تحت كلٍّ من P و S. عندئذٍ، يكون نوعا الحل الأول والثاني هما طرفا الخط العلوي والسفلي على التوالي، أما نوع الحل الثالث فهو انتهاك شرط زيادة الجهد على طول الحواف. إذا انتُهك هذا الشرط الأخير، فقد لا تُعظِّم نقطة النهاية الجهد على الخط. لذلك، فإن المسألة كلية: إما أن يُعثر على حل، أو يُعثر على برهان موجز على عدم تحقق الشروط.

يُعرَّف UEOPL بشكل مشابه جدًا، ولكن يُفترض وجود خط واحد فقط. لذا، فإن إيجاد النوع الثاني من الحلول المذكورة أعلاه سيُخالف الوعد الذي يضمن تفرد النوع الأول من الحلول. تمت إضافة نوع رابع من الحلول لتوفير طريقة أخرى للكشف عن وجود خط ثانٍ.

• نقطتان x و y بحيث​${\displaystyle x\neq y,x\neq S(x),y\neq S(y)}$و إما​${\displaystyle C(x)=C(y)}$أو​​${\displaystyle C(x)<C(y)<C(S(x))}$⁠ .

يشير هذا النوع من الحلول إما إلى أن x و y يقعان على خطين مختلفين، أو إلى انتهاك شرط أن القيم على الخط نفسه تتزايد بشكل صارم. وتكمن ميزة تضمين هذا الشرط في أنه قد يكون من الأسهل إيجاد x و y المطلوبين بدلاً من إيجاد بداية خطوطهما، أو من وجود انتهاك صريح لشرط التكلفة المتزايدة.

تتضمن مجموعة مسائل UEOPL، من بين مسائل أخرى، مسألة حل مصفوفة P - مسألة التكامل الخطي ، ^{[ 11 ]} وإيجاد نقطة تصريف ذات اتجاه تصريف فريد في المكعبات، ^{[ 11 ]} وحل لعبة عشوائية بسيطة ^{، [ 11 ]} ومسألة شطيرة α-Ham. ^{[ 14 ]} تشمل المسائل الكاملة في UEOPL مسألة نهاية خط الجهد الفريد، وبعض متغيراتها التي تتزايد فيها التكاليف بمقدار 1 بالضبط أو حالة بدون دائرة P ، ومسألة الانكماش المنفصل بالتبديل الواحد. ^{[ 11 ]}

تُغطي لغة EOPL مشاكل البحث المشابهة لتلك الموجودة في UEOPL، مع استثناء يسمح بوجود أسطر متعددة، ويتم البحث فيها عن أي نهاية للسطر. لا توجد حاليًا أي مشاكل معروفة موجودة في EOPL وغير موجودة في UEOPL.

تُعدّ EOPL فئة فرعية من CLS، ولا يُعرف ما إذا كانتا متطابقتين أم لا. وتُعتبر UEOPL جزءًا لا يتجزأ من EOPL.

FP (اختصارًا لـ "Function Polynomial") هي فئة من مسائل الدوال التي يمكن حلها في وقت متعدد الحدود حتمي. ${\displaystyle {\mathsf {FP}}\subseteq {\mathsf {CLS}}}$ويُفترض أن هذا الإدراج صارم. تمثل هذه الفئة فئة مسائل الدوال التي يُعتقد أنها قابلة للحل حسابيًا (بدون عشوائية). إذا كانت TFNP = FP، فإن${\displaystyle {\mathsf {P}}={\mathsf {NP}}\cap {\mathsf {coNP}}}$، وهو أمر بديهي بالنظر إلى حقيقة أن${\displaystyle {\mathsf {TFNP}}={\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$ومع ذلك، يُعتقد عمومًا أن${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}\cap {\mathsf {coNP}}}$وبالتالي فإن TFNP ≠ FP.