DLOGTIME

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

انظر كذلك

مراجع

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

إضافةً إلى ذلك، الاستخدام الأول هو تعريف التعقيد DLOGTIME-uniformty والذي هو مهم في تعقيد الدوائر البوليانية .

من جهة ثانية، تعريف اختصار بحيث يكون ملائما لكل الاقسام المعروفة مستغلين في هذا ضعف DLOGTIME ,