كتب strong and narrow polynomial
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
بقوة وضيق كثير الحدود (معلومة)
في بعض السياقات، وخاصة في التحسين ، واحد يفرق بين وقت متعدد الحدود بقوة و الوقت متعدد الحدود ضعيفة الخوارزميات. هذان المفهومان لهما صلة فقط إذا كانت المدخلات إلى الخوارزميات تتألف من الأعداد الصحيحة.
يتم تحديد وقت كثير الحدود كثيرًا في النموذج الحسابي للحساب. في هذا النموذج من الحساب، تأخذ العمليات الحسابية الأساسية (الجمع والطرح والضرب والقسمة والمقارنة) خطوة زمنية للوحدة، بغض النظر عن أحجام المعاملات. الخوارزمية تعمل في زمن كثير الحدود جدا
- يحدّد عدد العمليات في النموذج الحسابي للحساب بمتعدد الحدود في عدد الأعداد الصحيحة في مثيل المدخلات ؛ و
- المساحة التي تستخدمها الخوارزمية يحدها كثيرات الحدود في حجم المدخلات.
يمكن تحويل أي خوارزمية لهذين الخواص إلى خوارزمية زمن متعددة الحدود عن طريق استبدال العمليات الحسابية بخوارزميات مناسبة لأداء العمليات الحسابية على جهاز Turing . إذا لم يتم الوفاء بالمتطلبات الثانية المذكورة أعلاه، فهذا غير صحيح بعد الآن. وبالنظر إلى العدد الصحيح (الذي يأخذ مساحة تتناسب مع n في نموذج آلة تورينج) ، فمن الممكن حساب مع مضاعفات n باستخدام تربيع متكرر. ومع ذلك، فإن المساحة المستخدمة لتمثيل تتناسب مع، وبالتالي الأسية بدلا من كثيرات الحدود في المساحة المستخدمة لتمثيل المدخلات.وبالتالي، ليس من الممكن تنفيذ هذا الحساب في زمن كثير الحدود على جهاز Turing ، ولكن من الممكن حسابه من خلال العديد من العمليات الحسابية.
على العكس من ذلك، هناك خوارزميات تعمل في عدد من خطوات آلة تورينج التي تحدها حدود متعددة في طول المدخلات المشفرة الثنائية، ولكنها لا تأخذ عددًا من العمليات الحسابية يحدها كثيرات الحدود في عدد أرقام الإدخال. ومن بين الأمثلة على ذلك خوارزمية الإقليدية في حساب القاسم المشترك الأكبر لعندين صحيحين. وبالنظر إلى اثنين الأعداد الصحيحة ويحدها وقت تشغيل الخوارزمية من قبل عدد من الخطوات آلة تورينج هذا هو متعدد الحدود في حجم تمثيل ثنائي و.وفي نفس الوقت، لا يمكن تقييد عدد العمليات الحسابية بعدد الأعداد الصحيحة في المدخلات (وهو ثابت في هذه الحالة، فهناك دائمًا عدد صحيح فقط من المدخلات). نظرًا إلى الملاحظة الأخيرة، لا تعمل الخوارزمية في وقت كثير الحدود. وقتها تشغيل الحقيقي يعتمد على مقادير من ووليس فقط على عدد من الأعداد الصحيحة في المدخلات.
ويقال إن الخوارزمية التي تعمل في زمن كثير الحدود لكنها ليست متعددة الحدود بقوة تعمل في زمن كثير الحدود . ومن الأمثلة المعروفة على المشكلة التي تعرف بها خوارزمية زمن ضيق كثير الحدود، ولكن من غير المعروف أنها تقبل خوارزمية زمن متعدد الحدود بشدة، هي البرمجة الخطية . لا ينبغي الخلط بين زمن الضيق في كثير الحدود والوقت الزائف متعدد الحدود.
