DLOGTIME
يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يناير 2022)
في علم التعقيد DLOGTIME هو قسم المسائل التي يمكن حلها بواسطة آلة تيورنج ,ذات وصول عشوائي ,حتمية حيث أن وقت حساب آلة تيورنج هو ((O(log(n. هذا يعني أنَّ الآلة سوف تتجاهل المُدخل ما عدا ((O(log(n منه , ويعد هذا القسم من اضعف الاقسام المعروفة إذ انه اصغر قسم ليس بديهيا معروف كما أن كل الاقسام الأخرى تحويه، أحد المسائل التي يمكن اعتبارها تابعة لهذا القسم هي فحص طول المُدخل بمساعدة البحث الثنائي , هنالك استخدامات لهذا القسم :
- الاستخدام الأول هو تعريف التعقيد DLOGTIME-uniformty والذي هو مهم في تعقيد الدوائر البوليانية .
- تعريف اختصار بحيث يكون ملائما لكل الاقسام المعروفة مستغلين في هذا ضعف DLOGTIME ,
فلتكن f تحويلة (transformation) كثيرة الحدود من المسألة X للمسألة Y نقول أنَّ f هي تحويلة DLOGTIME إذا اللغة {(x,i,c): البت في المكان i في (f(x هو c } تابعة ل-DLOGTIME
مراجع
[عدل]انظر أيضا
[عدل]أقسام التعقيد المهمة | |
|---|---|
| ممكنة للتنفيذ | |
| مشكوك في إمكانية تنفيذها |
|
| غير قابل للتنفيذ | |
| أقسام هرمية |
|
| عائلات اقسام |
|
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Credit:
(see original file).
