Kelas kompleksitas yang dimasukkan dengan benar dalam DLOGTIME

8

Apakah ada masalah keputusan yang ada dalam kelas kompleksitas yang termasuk dalam DLOGTIME? (kecuali , tentu saja)O(1)

Jika ada, dapatkah kita membuat masalah lengkap untuk DLOGTIME? Jadi, bisakah ada pengurangan dengan atau lebih kecil?O(log(logn))

pengguna2346
sumber

Jawaban:

3

Regan & Vollmer menyarankan dalam kesimpulan makalah terkait bahwa kelas-kelas seperti itu dapat dibangun (meskipun fiddly). Makalah itu sendiri tentang LOGTIME, dan menyebutkan di mana perubahan harus dilakukan untuk menyesuaikan hasil dengan LOGLOGTIME, LOGLOGLOGTIME dll, tetapi tidak secara eksplisit menunjukkan hasilnya.

Luke Mathieson
sumber