سؤال يتعلق بتعريف الوقت الفرعي الحتمي (SUBEXP)

Question

إلقاء نظرة الأولى على تعريف subexp من حديقة حيوان التعقيد:

subexp: (حتمية الفرعية الأفقية) تقاطع dtime ( $ 2 ^ ^ {n ^ \ epsilon} $ ) على جميع $ \ Epsilon $ > 0. (لاحظ أن الخوارزمية المستخدمة قد تختلف مع $ \ Epsilon $ $ \ bigcap _ {\ epsilon> 0} $ dtime $ (2 ^ {n ^ \ epsilon}) $ .

لذلك، أحضر تعريف التسهيل الذي هو:

exp= $ \ bigcup_ {k \ geq 1} $ dtime $ (2 ^ {n ^ k}) $

تعريف EXP واضح، لأنه يتضمن كل متعدد الحدود من N إلى قوة 2. (على سبيل المثال $ 2 ^ ^ {30}} $ أو 100 دولار ^ {n ^ {99}} $ etc.)

السؤال الأول: ما هو مجال $ \ Epsilon $ ؟ أعتقد أنه يتراوح بين 0 و 1 لكنه لم يحدد في التعريف. هل من المعتاد أنه عندما يكون لدينا $ \ Epsilon $ ثم يعني ذلك بين 0 و 1.

السؤال الثاني: الآن، في حالة Subexp، ليس من الواضح كيف يعني التعريف عن التقاطع؟ أعني، لا ينبغي كتابتها على النحو التالي: $ \ bigcup_ {1> \ epsilon> 0} $ dtime $ (2 ^ {n ^ \ epsilon}) $ . على سبيل المثال حسب التعريف فوق ما تقاطع: $ 2 ^ ^ {0.01}} {bigcap 2 ^ {n ^ {0.02}}؟ $

سؤال ثالث: هناك تعريفان subexp في wikipedia ، هو هناك تعريف يستغرق كله الفرعي أو لا نقوم بهذا لهذا السبب لدينا تعريفان.

شكرا لك!

Answer 1

في تعريف subexp، $ \ epsilon $ يتراوح على كل الحقائق الإيجابية. ولكن تحصل على نفس التعريف إذا طلبت ذلك $ \ Epsilon <\ epsilon_0 $ ، للحصول على $ \ Epsilon_0> 0 $ من اختيارك؛ إذا طلبت $ \ Epsilon $ تكون عقلانية؛ إذا كنت تذهب فقط $ \ Epsilon= 1 / n $ ؛ وما إلى ذلك وهلم جرا. وذلك لأن dtime هو روتونتون: إذا كان $ f \ leq g $ ثم $ \ mathsf {dtime} (f) \ subseteq \ mathsf {dtime} (g) $ .

تعريف بديل ل Subexp سيكون: $$ \ mathsf {subexp}=bigcup_ {g (n)= o (1)} \ mathsf {dtime} (2 ^ {n ^ {g (n)}})، $ غالبا ما تشير ببساطة عن طريق $ \ mathsf {dtime} (2 ^ {n ^ {o (1)}}) $ .

بعض الأمثلة: $ \ mathsf {p} \ subseteq \ mathsf {subexp} $ ؛ وظيفة يمكن حسابها في الوقت المناسب 2 ^ ^ ^ {n ^ {1 / \ log \ log n} $ موجودة في $ \ mathsf {subexp} $ ؛ وظيفة يمكن حسابها في الوقت المناسب $ 2 ^ ^ {\ log ^ {10} n} $ في $ \ mathsf {subexp} $ .

على النقيض من ذلك، وظيفة يمكن حسابها في الوقت المناسب $ 2 ^ ^ {1/10}} $ ليست بالضرورة في $ \ mathsf {subexp} $ time التسلسل الهرمي، هناك وظيفة هذه الوظيفة التي تكمن خارج $ \ mathsf {subexp} $ ).

وظيفة في $ \ mathsf {dtime} (2 ^ {n / \ log n}) $ يكمن في subpt ولكن ليس بالضرورة في subexp.