Esta pregunta es acerca de sofisticación, una manera de medir la cantidad de "interesante, no aleatoria de la información" en una cadena binaria, el cual fue propuesto por la prueba de Kolmogorov y otros en la década de 1980. Voy a definir todos los conceptos a continuación, pero para leer más, recomiendo este papel por Antunes y Fortnow, esta tesis doctoral por Antunes, o este papel por Gacs, Tromp, y Vitanyi.
Dada una n-cadena de bits x, recordemos que K(x), el test de Kolmogorov complejidad de x es la longitud en bits de la más corta del programa de p (en algunos fijos universal lenguaje de programación) tales que p()=x, es decir, p detiene y salidas de x cuando se le da una entrada en blanco. Dado un conjunto S ⊆ {0,1}n, también se puede definir K(S) para la longitud en bits de la más corta del programa que emite la 2de nbits característicos de la secuencia de S. Finalmente, se puede definir K(x|S) para la longitud en bits de la más corta del programa de p tales que p(S)=x, es decir, p detiene y salidas de x cuando se alimenta de la característica de la secuencia de S como entrada.
El "problema" con el test de Kolmogorov complejidad es que es maximizada por azar cadenas, que son intuitivamente no muy "complejo" en absoluto. Esto motiva las siguientes alternativas para K(x):
Dada una n-cadena de bits x y una constante c>0, la oxymoronically nombre ingenuo sofisticación de x, o NSophc(x), es el menor valor posible de K(S), a través de todos los conjuntos S ⊆ {0,1}n tal que x∈S y K(x|S) ≥ log2|S| c). Intuitivamente, NSoph mide el número mínimo de bits necesarios para especificar un conjunto de que x es un incompresible o test de Kolmogorov-elemento aleatorio. Yo lo llamo "ingenuo" porque es la primera medida me gustaría pensar que algo así como la complejidad de Kolmogorov, pero pequeño en el que el azar cadenas (pequeño, porque para el azar cadenas, uno puede tomar S={0,1}n, de donde NSophc(x)=O(1)).
Mientras tanto, el grueso de la sofisticación de x o CSoph(x), definida por Antunes, es el menor valor posible de 2K(S)+log2|S|-K(x), a través de todos los conjuntos S ⊆ {0,1}n tal que x∈S. Intuitivamente, CSoph mide el número mínimo de bits necesarios para especificar x a través de un "código de dos partes, donde la primera parte especifica un conjunto S que contiene x, la segunda parte da el índice de x en S, y una penalización que se aplica tanto para K(S) (la longitud de la primera parte del código) y de K(S)+log2|S|-K(x) (la cantidad por la cual el total de la longitud del código supera K(x)). A pesar de los pesados definición, Antunes se dispersan por la evidencia de que CSoph es, en diversas formas en que el "derecho" a la medida de la no-aleatorio de la información en una cadena.
Mi pregunta ahora es la siguiente:
Vamos a c=O(1). Es NSophc(x), mi "sofisticados tipo de sofisticación," siempre cerca de CSoph(x), Antunes' "sofisticado tipo de sofisticación"? O puede haber una gran diferencia entre los dos? Si es así, cómo es de grande?
Aquí es lo que yo sé acerca de esta pregunta:
- CSoph(x) ≤ 2NSophc(x)+c. Para ver esto: dejar que el conjunto S de minimizar K(S) sujeto a x∈S y K(x|S) ≥ log2|S| c). Luego CSoph(x) ≤ 2K(S)+log2|S|-K(x) ≤ 2NSophc(x)+log2|S|-K(x) ≤ 2NSophc(x)+log2|S|-K(x|S) ≤ 2NSophc(x)+c.
- NSophc(x) puede ser de alrededor de dos veces tan grande como CSoph(x). Para ver esto: en primer lugar, como se observa por Antunes, si x es una n-cadena de bits, entonces CSoph(x) nunca excede de n/2+o(n). (Por siempre podemos lograr que obligado por la configuración de S={x} si K(x)≤n/2, o S={0,1}n si K(x)>n/2.) Segundo, como se discutió por Gacs, Tromp, Vitanyi, es posible la construcción de lo que el test de Kolmogorov llamado "absolutamente no-objetos al azar," significado de n-bits cadenas de x tal que K(x|S) ≤ log2|S| - O(1) siempre que K(S) ≤ n - zueco(n). Para estas cadenas, que claramente tienen NSophc(x) ≥ no(log n) si c=O(1). La combinación de ahora se obtiene el resultado.
Como nota final, NSoph y CSoph son tanto diferente de la ordinaria de la sofisticación" Soph, que se define como sigue: Sophc(x) es el menor valor posible de K(S), a través de todos los conjuntos S ⊆ {0,1}n tal que x∈S y K(S) + log2|S| ≤ K(x)+c. Intuitivamente, Sophc(x) mide el número mínimo de bits necesarios para la primera parte de una cerca de mínimos de dos partes de código que especifica la cadena x. Se puede observar el siguiente (voy a dar detalles sobre la petición):
- NSophc(x) ≤ Sophc(x)
- CSoph(x) ≤ Sophc(x)+c
- Existen cadenas de x para los cuales Sophc(x) es muy grande pero NSophc(x) y CSoph(x) son muy pequeñas.
Yo también voy a observar que NSophc(x), CSoph(x), y Sophc(x) son todos los de la superior-limitada por la complejidad de Kolmogorov K(x) (o, más bien, por K(x)+c).
Actualización: lo Siento, sólo unos minutos después de escribir este post, creo ver la respuesta a una dirección de mi problema! Considerar el "absolutamente no-aleatoria de los objetos" x discutido anteriormente. Estos objetos satisfacer K(x) ≥ NSophc(x) ≥ no(log n). Pero precisamente debido a su complejidad de Kolmogorov es tan grande, que también debe satisfacer CSoph(x)=O(log n), se logra mediante el establecimiento de S={0,1}n. Por otro lado, aún no sé si CSoph(x) nunca puede ser mayor que NSophc(x) (sólo que, si es así, nunca es más que un factor de 2 grandes). Y yo todavía estaría muy interesado si alguien pudiera responder a esa pregunta.
