Existe-t-il des problèmes «O (1) -complet»?

De nombreuses classes de complexité ont des problèmes "complets". Existe-t-il des problèmes complets pour la classe de complexité des problèmes qui peuvent être résolus en temps ?$O(1)$

Une complication est que cette classe dépend du modèle de calcul; un problème peut être résolu en temps dans un modèle de calcul raisonnable mais pas dans un autre, étant donné que "raisonnable" signifie généralement l'équivalence de temps polynomial avec une machine de Turing. Cependant, il pourrait encore être élaboré pour des modèles raisonnables spécifiques.$O(1)$

Je pense qu'il est plus logique d'examiner les réductions de plusieurs à temps constant. Cependant, je suis également disposé à envisager d'autres réductions raisonnables s'il existe de la documentation à leur sujet.

Existe-t-il quelque chose comme cela, ou a-t-il été étudié, pour un modèle de calcul?

Comme la lecture de l'entrée est nécessaire pour presque tous les problèmes, nous avons besoin d'au moins temps pour presque tous les problèmes, où est la taille de l'entrée. Par conséquent, vous pouvez penser à la classe des problèmes de temps linéaire, qui est déjà définie.$\Omega(n)$$n$

Cependant, nous ne connaissons toujours pas de problème -complete ou -complete. Le domaine de la complexité fine a de nouveaux résultats dans ce domaine, mais les classes sont basées sur des problèmes (par exemple, APSP est équivalent à Radius, Negative Triangle, ...).O ( n 2$O(n)$$O(n^2)$

Je pense que pour les problèmes , tous les langages sont complets sous "réductions à temps constant" sauf etL = Σ ∗ L = $O(1)$$L = \Sigma^*$$L = \emptyset$

Supposons que etL ≠ 0 , L ≠ Σ $L, L' \in O(1)$$L \neq 0, L \neq \Sigma^*$

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

Il s'agit d'une réduction en temps constant de à :$L'$$L$

• étant donné résoudre en le tempsL ′ O ( 1 $x$$L'$$O(1)$
• si alors sortie , sinon sortiex Y x $x \in L'$$x_Y$$x_N$

Donc est complet pour (... réduction paresseuse, résultat paresseux :-)).O ( 1 $L$$O(1)$