La definición de la complejidad de Komolgrov para una cadena S dada y para un lenguaje de programación dado L es el programa P más corto de tal manera que P, cuando se presenta sin entradas, generará S. Sin embargo, podría darse el caso de que el valor n = | S El | se proporciona como una entrada adicional y viene “sin costo” con respecto a la duración del programa P.
Gilad Tsur sugiere que la diferencia máxima es O (log (n)) porque, después de todo, podría generar n como un número binario y luego continuar desde allí con el resto del programa. Esto, al menos, es una interpretación del enunciado del problema.
Otra interpretación, y esto dependerá del contexto en el que se le presente el enunciado del problema, es que está interesado en descubrir la complejidad de Komolgrov para una clase de cadenas C, de modo que haya algún predicado C-pred donde S sea miembro de la clase C si y solo si C-pred acepta S. En este caso, puede preguntar sobre la complejidad máxima para cualquier cadena en la clase, o la expectativa sobre la complejidad, etc. En este caso, la presentación de la longitud n es simplemente parte del predicado: limite su clase de cadenas C a solo aquellas en las que incluya la condición de que | S | = n.
- Cómo encontrar correspondencia en dos imágenes en las que los objetos son bolas del mismo tamaño y color
- Cómo configurar una computadora que básicamente se ejecuta fuera de una carpeta de red
- ¿Qué es la planificación del discurso?
- ¿Cuál es la reputación del programa de informática de Cornell, en comparación con otros programas principales? ¿Qué tan bueno es Cornell con trabajos en grandes empresas tecnológicas (por ejemplo, Facebook, etc.), frente a Carnegie Mellon o Stanford?
- ¿Qué es una tienda distribuida de valor-clave? ¿Cuál fue la motivación para diseñarlo en primer lugar?
La interpretación de Gilad Tsur suele ser más común, pero también puede encontrar la otra interpretación.
