Çift üstel sorunlar?

Question

Bilgisayar bilimlerinde sadece double exponential zamanında çözülebilen önemli bir sorun var mı? Ve eğer varlarsa o zaman hangi sınıflara aittirler? Wikipedia itibaren

Answer 1

:

hesaplama karmaşıklığı Teoride, bazı algoritmalar çift üstel zaman alır:

• Presburger aritmetik için her karar prosedürü kanıtlanabilir en azından çift üstel zaman gerektirir

• Bir alan üzerinde bir Gröbner temeli hesaplamak. En kötü durumda, bir Gröbner temeli, değişken sayısında iki katına çıkabilen bir dizi öğeye sahip olabilir. ilişkisel değişmeli birlefltiriciler komple bir set bulma

• karşılanması CTL + (ki, 2-EXPTIME tamamlama aslında) gerçek kapalı alanlarda

• Nicelik eleme doubly üstel alır zaman (bkz. Silindirik cebirsel ayrışma).

• Normal ifadenin tamamlayıcısı hesaplanması