DLOGTIME

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في علم التعقيد DLOGTIME هو قسم المسائل التي يمكن حلها بواسطة آلة تيورنج ,ذات وصول عشوائي ,حتمية حيث أن وقت حساب آلة تيورنج هو ((O(log(n . هذا يعني أنَّ الالة سوف تتجاهل المُدخل ما عدا ((O(log(n منه , ويعد هذا القسم من اضعف الاقسام المعروفة اذ انه اصغر قسم ليس بديهيا معروف كما أن كل الاقسام الاخرى تحويه, أحد المسائل التي يمكن اعتبارها تابعة لهذا القسم هي فحص طول المُدخل بمساعدة البحث الثنائي , هنالك استخدامات لهذا القسم :

  1. الاستخدام الاول هو تعريف التعقيد DLOGTIME-uniformty والذي هو مهم في تعقيد الدوائر البوليانية .
  2. تعريف اختصار بحيث يكون ملائما لكل الاقسام المعروفة مستغلين في هذا ضعف DLOGTIME ,

    فلتكن f تحويلة (transformation) كثيرة الحدود من المسألة X للمسألة Y نقول أنَّ f هي تحويلة DLOGTIME اذا اللغة {(x,i,c): البت في المكان i في (f(x هو c } تابعة ل-DLOGTIME

انظر أيضا[عدل]

Wiki letter w.svg هذه بذرة تحتاج للنمو والتحسين، فساهم في إثرائها بالمشاركة في تحريرها.