كتب almost polynomial time
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
زمن شبه كثير الحدود (معلومة)
"خوارزميات الوقت شبه متعددة الحدود" هي خوارزميات يتم تشغيلها بشكل أبطأ من زمن كثير الحدود، ولكنها ليست بطيئة جدًا حتى تصبح وقتًا أسيًا. أسوأ حالة تشغيل وقت خوارزمية شبه متعددة الحدود هي لبعض ثابتة. إذا كان الثابت "c" في تعريف الخوارزميات الزمنية متعددة الحدود يساوي 1 ، نحصل على خوارزمية زمن متعددة الحدود، وإذا كان أقل من 1 ، نحصل على خوارزمية وقت خطي sub-timeear.
تنشأ خوارزميات الوقت شبه متعددة الحدود عادةً في التخفيضات من مشكلة NP-hard لمشكلة أخرى. على سبيل المثال، يمكن للمرء أن يأخذ مثالاً على مشكلة صلبة في NP ، على سبيل المثال 3SAT ، وتحويلها إلى مثيل لمشكلة أخرى B ، لكن حجم المثيل يصبح. في هذه الحالة، لا يثبت هذا الخفض أن المشكلة B هي NP-hard ؛ هذا التخفيض يظهر فقط أنه لا توجد خوارزمية زمن متعددة الحدود لـ B ما لم يكن هناك خوارزمية زمن متعددة الحدود لـ 3SAT (وبالتالي كل NP ). وبالمثل، هناك بعض المشاكل التي نعرف خوارزميات وقت شبه متعدد الحدود، ولكن لا توجد خوارزمية زمن متعددة الحدود.هذه المشاكل تنشأ في خوارزميات التقريب. مثال مشهور هو مشكلة شجرة ستاينر الموجهة، والتي يوجد بها خوارزمية تقريب زمني متعددة الحدود تحقق عامل تقريب لـ (n عدد الرؤوس) ، لكن إظهار وجود مثل هذه الخوارزمية متعددة الحدود الزمنية هو مشكلة مفتوحة.
ومن المشاكل الحسابية الأخرى مع حلول الوقت متعددة الحدود، ولكن لا يوجد حل زمني متعدد الحدود، تشمل مشكلة العصب المزروع الذي يتمثل الهدف فيه في العثور على زمرة كبيرة في اتحاد زمرة ورسم بياني عشوائي . على الرغم من أنه شبه متعدد الحدود قابلة للحل، فقد تم افتراض أن مشكلة العصب المزروع ليس لها حل زمني متعدد الحدود. وقد استخدم هذا التخمين زمرة زرعت بمثابة صلابة افتراض حسابي لإثبات صعوبة العديد من المشاكل الأخرى في الحسابية نظرية اللعبة ، اختبار الملكية ، و تعلم الآلة .
تتكون فئة QP المعقدة من جميع المشاكل التي تحتوي على خوارزميات زمنية متعددة الحدود. يمكن تعريفه من حيث DTIME على النحو التالي.
العلاقة مع NP- مشاكل كاملة
في نظرية التعقيد، تسأل مشكلة P مقابل PN غير المحلولة إذا كانت جميع المشاكل في NP تحتوي على خوارزميات متعددة الحدود الزمنية. جميع خوارزميات معروفة للمشاكل كاملة NP مثل 3SAT الخ تأخذ وقتا أسي. في الواقع، يتم تخمينه للعديد من المشاكل الطبيعية NP-complete التي لا تملك خوارزميات وقت أسي دون الألف. هنا، يُنظر إلى "الوقت الأسى الفرعي" ليعني التعريف الثاني المعروض أدناه. (من ناحية أخرى، فإن العديد من مشاكل الرسم البياني الممثلة بالطريقة الطبيعية من خلال المصفوفات المجاورة تكون قابلة للحل في وقت ما قبل التصنيع ببساطة لأن حجم المدخلات هو مربع عدد الرؤوس ) . هذا التخمين (لمشكلة k-SAT) معروف مثل فرضية الزمن الأسي. ولأنه من المتصور أن المشاكل الكاملة NP لا تحتوي على خوارزميات زمن متعددة الحدود، فإن بعض نتائج inapproximability في مجال خوارزميات التقريب تجعل الافتراض بأن مشكلات NP-complete لا تحتوي على خوارزميات زمن شبه متعددة الحدود. على سبيل المثال، راجع نتائج inapproximability المعروفة لمشكلة غطاء المجموعة.
