Existem problemas de “O (1) -completo”?

Muitas classes de complexidade têm problemas "completos". Existem problemas completos para a classe de complexidade dos problemas que podem ser resolvidos no tempo ?$O(1)$

Uma complicação é que essa classe depende do modelo de computação; um problema pode ser solucionado no tempo em um modelo razoável de computação, mas não em outro, dado que "razoável" normalmente significa equivalência de tempo polinomial com uma máquina de Turing. No entanto, ainda poderia ser elaborado para modelos razoáveis ​​específicos.$O(1)$

Eu acho que faz mais sentido olhar para reduções de muitos um em tempo constante. No entanto, também estou aberto a examinar outras reduções sensatas, se houver literatura sobre elas.

Existe algo assim, ou foi estudado, para algum modelo de computação?

Como a leitura da entrada é necessária para quase todos os problemas, precisamos de pelo menos tempo para quase todos os problemas, em que n é o tamanho da entrada. Portanto, você pode pensar na classe de problemas de tempo linear, que já está definida.$\Omega(n)$$n$

No entanto, ainda não conhecemos nenhum problema completo com ou O ( n 2 ) . O campo da complexidade refinada tem alguns resultados novos nessa área, mas as classes são baseadas em problemas (por exemplo, o APSP é equivalente a Radius, Negative Triangle, ...).$O(n)$$O(n^2)$

Eu acho que para problemas , todos os idiomas estão completos em "reduções de tempo constante", exceto L = Σ ∗ e L = $O(1)$$L = \Sigma^*$$L = \emptyset$

Suponha-se que e L ≠ 0 , L ≠ Σ $L, L' \in O(1)$$L \neq 0, L \neq \Sigma^*$

Seja $x_Y \in L, x_N \notin L$

Esta é uma redução de tempo constante de para L :$L'$$L$

• dado resolva L ′ em O ( 1 ) tempo$x$$L'$$O(1)$
• se , produza x Y , caso contrário, gera x $x \in L'$$x_Y$$x_N$

Então está completo para O ( 1 ) (... redução preguiçosa, resultado preguiçoso :-)).$L$$O(1)$