Apakah ada masalah “O (1) -complete”?

Banyak kelas kompleksitas memiliki masalah "lengkap". Apakah ada masalah lengkap untuk kelas kompleksitas masalah yang dapat diselesaikan dalam waktu ?$O(1)$

Suatu komplikasi adalah bahwa kelas ini tergantung pada model perhitungan; masalah dapat dipecahkan dalam waktu dalam satu model perhitungan yang masuk akal tetapi tidak pada yang lain, mengingat bahwa "masuk akal" biasanya berarti kesetaraan waktu polinomial dengan mesin Turing. Namun, itu masih bisa dikerjakan untuk model wajar tertentu.$O(1)$

Saya pikir paling masuk akal untuk melihat pengurangan banyak waktu secara konstan. Namun, saya juga terbuka untuk melihat pengurangan yang masuk akal lainnya jika ada literatur tentangnya.

Apakah ada yang seperti ini, atau sudah dipelajari, untuk model komputasi apa saja?

Karena membaca input diperlukan untuk hampir semua masalah, kita memerlukan setidaknya waktu untuk hampir semua masalah, di mana n adalah ukuran input. Oleh karena itu, Anda mungkin memikirkan kelas masalah waktu linier, yang sudah ditentukan.$\Omega(n)$$n$

Namun, kami masih belum mengetahui masalah lengkap -complete atau O ( n 2 ) . Bidang kompleksitas berbutir halus memiliki beberapa hasil baru di bidang ini, tetapi kelasnya berbasis masalah (misalnya, APSP setara dengan Radius, Segitiga Negatif, ...).$O(n)$$O(n^2)$

$O(1)$$L = \Sigma^*$$L = \emptyset$

$L, L' \in O(1)$$L \neq 0, L \neq \Sigma^*$

$x_Y \in L, x_N \notin L$

$L'$$L$

• $x$$L'$$O(1)$
• $x \in L'$$x_Y$$x_N$

$L$$O(1)$