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

لنفترض حل مشكلة اختبار ما إذا كان العدد n أوليًا عن طريق التحقق ببساطة مما إذا كان العدد في${\displaystyle \{2,3,\dots ,{\sqrt {n}}\}}$يقسم${\displaystyle n}$بالتساوي. قد يستغرق هذا النهج ما يصل إلى${\displaystyle {\sqrt {n}}-1}$القسمة، وهي شبه خطية في قيمة n ولكنها أسية في طول n (وهو ما يقارب${\displaystyle \log(n)}$على سبيل المثال، يتطلب عدد n أقل بقليل من 10,000,000,000 ما يقارب 100,000 عملية قسمة، على الرغم من أن طول n لا يتجاوز 11 رقمًا. علاوة على ذلك، يمكن بسهولة كتابة مُدخل (كعدد مكون من 300 رقم مثلاً) يجعل هذه الخوارزمية غير عملية. بما أن التعقيد الحسابي يقيس الصعوبة نسبةً إلى طول المُدخل (المُشفّر)، فإن هذه الخوارزمية البسيطة هي في الواقع أسية. ومع ذلك، فإن وقتها شبه متعدد الحدود .

قارن هذه الخوارزمية بخوارزمية عددية متعددة الحدود حقيقية - على سبيل المثال، خوارزمية الجمع البسيطة: جمع عددين مكونين من 9 أرقام يستغرق حوالي 9 خطوات بسيطة، وبشكل عام، تكون الخوارزمية خطية تمامًا بالنسبة لطول المدخلات. بالمقارنة مع الأعداد الفعلية التي يتم جمعها (بالمليارات)، يمكن تسمية الخوارزمية بـ "زمن شبه لوغاريتمي"، على الرغم من أن هذا المصطلح ليس شائعًا. وبالتالي، فإن جمع أعداد مكونة من 300 رقم ليس بالأمر المستحيل. وبالمثل، فإن القسمة المطولة هي عملية تربيعية: يمكن قسمة عدد مكون من m رقم على عدد مكون من n رقم في${\displaystyle O(mn)}$الخطوات (انظر ترميز Big O. )

في حالة الأعداد الأولية، اتضح أن هناك خوارزمية مختلفة لاختبار ما إذا كان n عددًا أوليًا (تم اكتشافها في عام 2002) تعمل في وقت${\displaystyle O((\log {n})^{6})}$.

في مسألة حقيبة الظهر ، لدينا${\displaystyle n}$أغراض ذات وزن${\displaystyle w_{i}}$والقيمة${\displaystyle v_{i}}$بالإضافة إلى الحد الأقصى لوزن حقيبة الظهر${\displaystyle W}$الهدف هو حل مشكلة التحسين التالية؛ بشكل غير رسمي، ما هي أفضل طريقة لوضع العناصر في حقيبة الظهر لتحقيق أقصى قيمة؟

أقصى${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

رهناً بـ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$و${\displaystyle x_{i}\in \{0,1\}}$.

حل هذه المشكلة صعب من فئة NP ، لذا فإن خوارزمية ذات زمن متعدد الحدود مستحيلة إلا إذا كانت P = NP . ومع ذلك،${\displaystyle O(nW)}$يمكن استخدام خوارزمية الوقت باستخدام البرمجة الديناميكية ؛ لأن العدد${\displaystyle W}$الاحتياجات فقط${\displaystyle \log W}$من بين الأمور التي يجب وصفها، تعمل هذه الخوارزمية في وقت شبه متعدد الحدود.