Medida limitada por recursos

La medida de recursos limitados de Lutz es una generalización de la medida de Lebesgue a clases de complejidad . Fue desarrollada originalmente por Jack Lutz . Así como la medida de Lebesgue proporciona un método para cuantificar el tamaño de subconjuntos del espacio euclidiano.${\displaystyle \mathbb {R} ^{n}}$La medida de recursos limitados proporciona un método para clasificar el tamaño de subconjuntos de clases de complejidad.

Por ejemplo, los informáticos generalmente creen que la clase de complejidad P (el conjunto de todos los problemas de decisión resolubles en tiempo polinomial ) no es igual a la clase de complejidad NP (el conjunto de todos los problemas de decisión verificables, pero no necesariamente resolubles, en tiempo polinomial). Dado que P es un subconjunto de NP, esto significaría que NP contiene más problemas que P. Una hipótesis más fuerte que " P no es NP " es la afirmación "NP no tiene medida p 0". Aquí, la medida p es una generalización de la medida de Lebesgue a subconjuntos de la clase de complejidad E , en la que P está contenida. Se sabe que P tiene medida p 0, por lo que la hipótesis "NP no tiene medida p 0" implicaría no solo que NP y P son desiguales, sino que NP es, en un sentido de teoría de la medida , "mucho mayor que P".

${\displaystyle \{0,1\}^{\infty }}$es el conjunto de todas las secuencias binarias infinitas . Podemos ver un número real en el intervalo unitario como una secuencia binaria infinita, considerando su expansión binaria . También podemos ver un lenguaje (un conjunto de cadenas binarias ) como una secuencia binaria infinita, estableciendo el n -ésimo bit de la secuencia en 1 si y solo si la n -ésima cadena binaria (en orden lexicográfico ) está contenida en el lenguaje. Por lo tanto, los conjuntos de números reales en el intervalo unitario y las clases de complejidad (que son conjuntos de lenguajes) pueden verse como conjuntos de secuencias binarias infinitas, y por lo tanto las técnicas de la teoría de la medida utilizadas para medir el tamaño de conjuntos de números reales pueden aplicarse para medir clases de complejidad. Sin embargo, dado que cada clase de complejidad computable contiene solo un número contable de elementos (porque el número de lenguajes computables es contable), cada clase de complejidad tiene una medida de Lebesgue de 0. Por lo tanto, para hacer teoría de la medida dentro de las clases de complejidad, debemos definir una medida alternativa que funcione de manera significativa en conjuntos contables de secuencias infinitas. Para que esta medida sea significativa, debe reflejar algo sobre la definición subyacente de cada clase de complejidad; Es decir, que se definen por problemas computacionales que pueden resolverse dentro de un límite de recursos determinado.

La base de la medida con recursos limitados es la formulación de martingalas de Ville . Una martingala es una función${\displaystyle d:\{0,1\}^{*}\a [0,\infty )}$de tal manera que, para todas las cadenas finitas w ,

${\displaystyle d(w)={\frac {d(w0)+d(w1)}{2}}}$.

(Esta es la definición original de Ville de una martingala, posteriormente ampliada por Joseph Leo Doob ). Se dice que una martingala d tiene éxito en una secuencia.${\displaystyle S\in \{0,1\}^{\infty }}$si${\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,}$dónde${\displaystyle S\upharpoonright n}$son los primeros n bits de S. Una martingala tiene éxito en un conjunto de secuencias.${\displaystyle X\subseteq \{0,1\}^{\infty }}$si tiene éxito en cada secuencia de X.

Intuitivamente, una martingala es un jugador que comienza con una cantidad finita de dinero (por ejemplo, un dólar). Lee una secuencia de bits indefinidamente. Después de leer el prefijo finito${\displaystyle w\in \{0,1\}^{*}}$, apuesta parte de su dinero actual a que el siguiente bit será un 0, y el resto de su dinero a que el siguiente bit será un 1. Duplica el dinero que se apostó al bit que aparece a continuación, y pierde el dinero apostado al bit que no apareció. Debe apostar todo su dinero, pero puede "no apostar nada" colocando la mitad de su dinero en cada bit. Para una martingala d , d ( w ) representa la cantidad de dinero que d tiene después de leer la cadena w . Aunque la definición de una martingala hace que la martingala calcule cuánto dinero tendrá, en lugar de calcular qué apuestas colocar, debido a la naturaleza restringida del juego, el conocimiento de los valores d ( w ), d ( w0 ) y d ( w1 ) es suficiente para calcular las apuestas que d colocó en 0 y 1 después de ver la cadena w . El hecho de que la martingala sea una función que toma como entrada la cadena vista hasta ahora significa que las apuestas colocadas son únicamente una función de los bits ya leídos; ninguna otra información puede afectar las apuestas (otra información es la llamada filtración en la teoría generalizada de las martingalas ).

El resultado clave que relaciona la medida con las martingalas es la observación de Ville de que un conjunto${\displaystyle X\subseteq \{0,1\}^{\infty }}$Un conjunto tiene medida de Lebesgue 0 si y solo si existe una martingala que tiene éxito en X. Por lo tanto, podemos definir un conjunto de medida 0 como aquel para el cual existe una martingala que tiene éxito en todos los elementos del conjunto.

Para extender este tipo de medida a clases de complejidad, Lutz consideró restringir la capacidad computacional de la martingala. Por ejemplo, si en lugar de permitir cualquier martingala, exigimos que sea computable en tiempo polinomial , obtenemos una definición de medida p: un conjunto de secuencias tiene medida p = 0 si existe una martingala computable en tiempo polinomial que tiene éxito en dicho conjunto. Definimos un conjunto con medida p = 1 si su complemento tiene medida p = 0. Por ejemplo, demostrar la conjetura anterior, de que NP no tiene medida p = 0, equivale a demostrar que ninguna martingala computable en tiempo polinomial tiene éxito en todo NP.

Un problema es casi completo para una clase de complejidad C si pertenece a C y "muchos" otros problemas de C se reducen a él. Más específicamente, el subconjunto de problemas de C que se reducen al problema es un conjunto de medida uno, en términos de la medida con recursos limitados. Este es un requisito menos estricto que el de que el problema sea completo para la clase.

• van Melkebeek, Dieter (2001), Aleatoriedad y completitud en la complejidad computacional , Springer, ISBN 3-540-41492-4Archivado del original el 19 de julio de 2011.

• Bibliografía de medidas con recursos limitados