زمن شبه متعدد الحدود

في نظرية التعقيد الحسابي وتحليل الخوارزميات ، يُقال إن الخوارزمية تستغرق وقتًا شبه متعدد الحدود إذا كان تعقيدها الزمني محدودًا بشكل شبه متعدد الحدود . أي أنه يجب أن يكون هناك ثابت${\displaystyle c}$بحيث يكون وقت تشغيل الخوارزمية في أسوأ الحالات ، على مدخلات بحجم${\displaystyle n}$، وله حد أعلى على النحو التالي $${\displaystyle 2^{O{\bigl (}(\log n)^{c}{\bigr )}}.}$$

تُعد مشاكل القرار ذات الخوارزميات شبه متعددة الحدود مرشحة طبيعية لتكون NP-متوسطة ، فهي ليست ذات وقت متعدد الحدود ولا من المحتمل أن تكون NP-صعبة .

تتألف فئة التعقيد QP من جميع المسائل التي لها خوارزميات ذات وقت شبه متعدد الحدود. ويمكن تعريفها بدلالة DTIME على النحو التالي. ^{[ 1 ]}

${\displaystyle {\mathsf {QP}}=\bigcup _{c\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{(\log n)^{c}}\right)}$

كان اختبار أدلمان-بوميرانس-روميلي للأعداد الأولية مثالًا مبكرًا على خوارزمية ذات زمن شبه متعدد الحدود . ^{[ 2 ]} ومع ذلك، فقد ثبت لاحقًا أن مشكلة اختبار ما إذا كان عدد ما عددًا أوليًا لها خوارزمية ذات زمن متعدد الحدود، وهي اختبار AKS للأعداد الأولية . ^{[ 3 ]}

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

• يمكن حل مسألة إيجاد أكبر مجموعة فرعية منفصلة من مجموعة أقراص الوحدة في المستوى الزائدي في وقت زمني${\displaystyle n^{O(\log n)}}$ويتطلب ذلك وقتاً${\displaystyle n^{\أوميغا (\log n)}}$في ظل فرضية الزمن الأسي. ^{[ 4 ]}
• يمكن حل مسألة إيجاد رسم بياني بأقل عدد من الرؤوس لا يظهر كرسم بياني فرعي مستحث من رسم بياني معطى في وقت زمني${\displaystyle n^{O(\log n)}}$ويتطلب ذلك وقتاً${\displaystyle n^{\أوميغا (\log n)}}$في ظل فرضية الزمن الأسي. ^{[ 5 ]}
• إيجاد أصغر مجموعة مهيمنة في بطولة . هذه المجموعة هي مجموعة جزئية من رؤوس البطولة التي تحتوي على حافة موجهة واحدة على الأقل إلى جميع الرؤوس الأخرى. يمكن حلها في وقت${\displaystyle n^{O(\log n)}}$ويتطلب ذلك وقتاً${\displaystyle n^{\أوميغا (\log n)}}$في ظل فرضية الزمن الأسي. ^{[ 6 ]}
• حساب بُعد فابنيك-تشيرفونينكيس لمجموعة من المجموعات . هذا هو حجم أكبر مجموعة${\displaystyle S}$(ليس بالضرورة داخل العائلة) التي تفككت بسبب العائلة، مما يعني أن كل مجموعة فرعية من${\displaystyle S}$يمكن تشكيلها عن طريق التقاطع${\displaystyle S}$مع أحد أفراد العائلة. يمكن حلها في الوقت المناسب${\displaystyle n^{O(\log n)}}$[ ^{7 ]} ويتطلب ذلك ^وقتاً${\displaystyle n^{(\log n)^{1/3-o(1)}}}$في ظل فرضية الزمن الأسي. ^{[ 8 ]}

تشمل المشاكل الأخرى التي تستغرق فيها أفضل خوارزمية معروفة وقتًا شبه متعدد الحدود ما يلي:

• مشكلة الزمرة المزروعة ، وهي تحديد ما إذا كان قد تم تعديل رسم بياني عشوائي عن طريق إضافة حواف بين جميع أزواج مجموعة فرعية من رؤوسه. ^{[ 9 ]}
• الازدواجية الرتيبة ، والعديد من المسائل المكافئة لتحويل الصيغ المنطقية بين الشكل الطبيعي الاقتراني والشكل الطبيعي الانفصالي، أو سرد جميع مجموعات التداخل الدنيا لعائلة من المجموعات، أو سرد جميع أغطية المجموعات الدنيا لعائلة من المجموعات، مع تعقيد زمني يُقاس بحجم المدخلات والمخرجات مجتمعة. ^{[ 10 ]}
• ألعاب التكافؤ ، التي تتضمن تمرير الرموز على طول حواف الرسم البياني الموجه الملون. ^{[ 11 ]} فازت الورقة البحثية التي تقدم خوارزمية شبه متعددة الحدود لهذه الألعاب بجائزة نيرود لعام 2021. ^{[ 12 ]}
• رسوم بيانية دائرية بثلاثة ألوان . هذه هي رسوم بيانية لتقاطع أوتار دائرة. إيجاد تلويناتها المثلى، بشكل عام، مسألة صعبة حسابيًا (NP-hard)، وكذلك اختبار إمكانية تلوينها بأربعة ألوان، ولكن يمكن إيجاد التلوينات بثلاثة ألوان في وقت زمني محدد.${\displaystyle n^{O(\log n)}}$[ ^{13 ]​}

تتضمن المشكلات التي تم الإعلان عن خوارزمية ذات وقت شبه متعدد الحدود لحلها ولكن لم يتم نشرها بالكامل ما يلي:

• مشكلة تماثل الرسم البياني ، التي تحدد ما إذا كان من الممكن جعل رسمين بيانيين متساويين عن طريق إعادة تسمية رؤوسهما، تم الإعلان عنها في عام 2015 وتم تحديثها في عام 2017 بواسطة لازلو باباي . ^{[ 14 ]}
• مشكلة فك العقدة ، التي تتمثل في التعرف على ما إذا كان مخطط العقدة يصف العقدة غير المفككة ، والتي أعلن عنها مارك لاكينبي في عام 2021. ^{[ 15 ]}

استُخدم الزمن شبه متعدد الحدود أيضًا لدراسة خوارزميات التقريب . وعلى وجه الخصوص، يُعد مخطط التقريب شبه متعدد الحدود (QPTAS) نوعًا مُعدَّلًا من مخطط التقريب متعدد الحدود، حيث يكون زمن تشغيله شبه متعدد الحدود بدلًا من متعدد الحدود. تشمل مسائل QPTAS التثليث بأقل وزن ، ^{[ 16 ]} وإيجاد الزمرة القصوى على الرسم البياني لتقاطع الأقراص، ^{[ 17 ]} وتحديد احتمالية انقطاع الرسم البياني الفائق عند فشل بعض حوافه باحتمالات مستقلة مُعطاة. ^{[ 18 ]}

وبعبارة أدق، فإن مشكلة إيجاد توازن ناش تقريبي لها تقريب شبه كامل متعدد الحدود (QPTAS)، ولكن لا يمكن أن يكون لها تقريب كامل متعدد الحدود (PTAS) في ظل فرضية الزمن الأسي. ^{[ 19 ]}