books sub distressing time
If you do not find what you're looking for, you can use more accurate words.
الوقت الأسى الفرعي (Info)
يستخدم مصطلح الزمن "الأسى الفرعي" للتعبير عن أن وقت تشغيل بعض الخوارزميات قد ينمو أسرع من أي حدود متعددة ولكنه لا يزال أصغر بكثير من الأس. وبهذا المعنى، فإن المشكلات التي لها خوارزميات زمنية ذات أبعاد فرعية هي أكثر قابلية للتتبع إلى حد ما عن تلك الخوارزميات الأسيّة فقط. لا يتم الاتفاق بوجه عام على التعريف الدقيق لـ "الأسى الفرعي" ، ونحن نذكر التعريفين الأكثر استخدامًا أدناه.
التعريف الأول
ويقال إن المشكلة تكون قابلة للحل الأسى الفرعي إذا كان من الممكن حلها في أوقات تشغيل تكون لوغاريتماتها أصغر من أي حدود متعددة. على نحو أدق، والمشكلة هي في الوقت المناسب دون الأسي إذا كان لكل لε > 0 يوجد خوارزمية الذي يحل المشكلة في O الوقت (2 ن ε ). مجموعة جميع هذه المشاكل هي فئة التعقيد SUBEXP والتي يمكن تعريفها من حيث DTIME على النحو التالي.
لاحظ أن هذا المفهوم للأسي الأسى غير منتظم من حيث ε بمعنى أن ε ليس جزءًا من المدخلات وقد يكون لكل have خوارزمية خاصة به لهذه المشكلة.
التعريف الثاني
يعرّف بعض المؤلفين الأزمنة الأسية الفرعية كأوقات جريان في 2 س ( ن ) . يسمح هذا التعريف بأوقات تشغيل أكبر من التعريف الأول للوقت الأسى الفرعي. مثال على مثل هذه الخوارزمية ذات الأسيّة الفرعية هي أفضل خوارزمية كلاسيكية معروفة لتحقيق عامل صحيح، المنخل العام لأعداد الأرقام، والذي يعمل في الوقت المناسب ، حيث يكون طول المدخلات n . "مثال آخر هو خوارزمية معروفة لمشكلة تشابه الرسم البياني ، والتي تعمل في الوقت المناسب .
لاحظ أنه يحدث فرقًا ما إذا كان يُسمح للخوارزمية أن تكون أسيةً فرعيةً في حجم المثيل ، أو عدد الرؤوس ، أو عدد الحواف. في التعقيد المعلمات ، يتم توضيح هذا الاختلاف عن طريق النظر في أزواج من مشاكل القرار والمعلمات k . ""SUBEPT هو فئة جميع المشاكل المعلمات التي تعمل في الوقت الأسي الفرعي في k ومتعدّد الحدود في حجم المدخلات n :
بتعبير أدق ، SUBEPT هو فئة من جميع المشاكل المعلمات التي لها دالة حسابية مع خوارزمية تقرر L في الوقت المناسب . دوال حسابية "
فرضية الزمن الأسي
على فرضية الوقت الأسي ( ETH ) هي أن 3SAT ، والمشكلة satisfiability من الصيغ المنطقية في نموذج عطف نظامي مع، على الأكثر، وثلاث الحرفية في بند ومع ن المتغيرات، لا يمكن حلها في الوقت المناسب 2 س ( ن ) . بتعبير أدق ، فإن الفرضية هي أن هناك بعض الثابت المطلق c > 0
بحيث لا يمكن تحديد 3SAT في الوقت المناسب 2 CN من قبل أي آلة تورينج حتمية. من خلال m تشير إلى عدد الفقرات ، تعادل ETH الفرضية القائلة بأنه لا يمكن حل k SAT في الوقت 2 o ( m ) لأي عدد صحيح k ≥ 3 . تعني الفرضية الزمنية الأسية P ≠ NP .
