Muchas clases de complejidad tienen problemas "completos". ¿Existen problemas completos para la clase de complejidad de problemas que se pueden resolver en el tiempo ?
Una complicación es que esta clase depende del modelo de cálculo; un problema puede resolverse en el tiempo en un modelo razonable de cómputo pero no en otro, dado que "razonable" generalmente significa equivalencia de tiempo polinómico con una máquina de Turing. Sin embargo, aún podría resolverse para modelos razonables específicos.
Creo que tiene más sentido mirar las reducciones múltiples de tiempo constante. Sin embargo, también estoy abierto a mirar otras reducciones sensatas si hay literatura sobre ellas.
¿Existe algo como esto, o ha sido estudiado, para algún modelo de computación?
fuente
Creo que para los problemas , todos los idiomas están completos bajo "reducciones de tiempo constante" excepto yL = Σ ∗ L = ∅O(1) L=Σ∗ L=∅
Suponga que yL ≠ 0 , L ≠ Σ ∗L,L′∈O(1) L≠0,L≠Σ∗
DejexY∈L,xN∉L
fuente