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

مراجع

انظر أيضا

أيقونة بذرة

هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها.