في نظرية التعقيد الحسابي ، يكون تقليل الوقت متعدد الحدود طريقة لحل مشكلة واحدة باستخدامآخر. كثيرًا ما تستخدم التخفيضات متعددة الحدود في نظرية التعقيد لتحديد فئات التعقيد والمشكلات الكاملة لتلك الفئات. …
ما الذي يعتبر وقت كثير الحدود؟
يقال أن الخوارزمية ذات وقت متعدد الحدود إذا كان وقت تشغيلها يحدها أعلى تعبير متعدد الحدود في حجم مدخلات الخوارزمية ، أي T (n)=O (nk)لبعض القيم الثابتة الإيجابية k.
كيف تعرف ما إذا كان شيء ما هو وقت متعدد الحدود؟
3 إجابات. تعد الخوارزمية متعددة الحدود (لها وقت تشغيل متعدد الحدود) إذا كان وقت تشغيلها على المدخلات ذات الحجم n هو Cnk على الأكثر بالنسبة لبعض k ، C>0. بالتساوي ، تعد الخوارزمية متعددة الحدود إذا كان وقت تشغيلها على مدخلات بحجم n هو O (nk) بالنسبة لبعض k>0.
ماذا يحدث إذا كان التخفيض مسموحًا به في الوقت الأسي؟
إذا كان التخفيض مسموحًا بالوقت الأسي ، فعندئذ يمكنه حل المشكلة الأصلية بالكامل وإنتاج مثيل تافه للمشكلة الهدفوهذا يعني أن كل مشكلة في NP يمكن اختزالها إلى كل مشكلة أخرى من خلال هذا النوع من التخفيضات ، لذلك فإن كل مشكلة في NP هي NP كاملة لتخفيضات الوقت الأسي.
ما هي الخوارزمية الأسية؟
يقال أن الخوارزمية هي الوقت الأسي ، إذا كان T (n) يحدها 2poly( ) ، حيث بولي (n) هي بعض كثيرة الحدود في n. بشكل أكثر رسمية ، الخوارزمية هي الوقت الأسي إذا كان T (n) يحدها O (2nk) لبعض ثابت k المرجع: Wiki.
