5
क्या कंप्यूटर विज्ञान में कोई महत्वपूर्ण समस्या है जिसे केवल double exponential समय में हल किया जा सकता है? और यदि वे मौजूद हैं तो किस वर्ग की समस्याएं हैं?डबल घातीय समस्याएं?
A
उत्तर
8
Wikipedia से:
कम्प्यूटेशनल जटिलता सिद्धांत में, कुछ एल्गोरिदम डबल घातीय समय लगेगा:
Presburger अंकगणित के लिए प्रत्येक निर्णय प्रक्रिया provably कम से कम डबल घातीय समय की आवश्यकता है
एक क्षेत्र में एक Gröbner आधार कंप्यूटिंग। सबसे बुरे मामले में, ग्रोबनेर आधार में कई तत्व हो सकते हैं जो चर की संख्या में दोगुना घातीय हो।
साहचर्य विनिमेय unifiers का एक पूरा सेट ढूँढना
संतोषजनक सीटीएल + (जो, वास्तव, 2-EXPTIME: पूर्ण में)
असली बंद कर दिया खेतों पर परिमाणक उन्मूलन एक दोगुना-घातीय लेता है समय (बेलनाकार बीजगणितीय अपघटन देखें)।
किसी रेगुलर एक्सप्रेशन का पूरक गिना जा रहा है