Ejemplos en los que el tamaño del alfabeto (

9

Sea un alfabeto, es decir, un conjunto finito no vacío. Una cadena es cualquier secuencia finita de elementos (caracteres) de . Como ejemplo, es el alfabeto binario y es una cadena para este alfabeto.Σ { 0 , 1 } 0110ΣΣ{0,1}0110

Por lo general, siempre que contenga más de 1 elemento, el número exacto de elementos en no importa: en el mejor de los casos, terminamos con una constante diferente en alguna parte. En otras palabras, realmente no importa si usamos el alfabeto binario, los números, el alfabeto latino o Unicode.ΣΣΣ

¿Hay ejemplos de situaciones en las que importa qué tan grande es el alfabeto?

La razón por la que estoy interesado en esto es porque me topé con uno de esos ejemplos:

Para cualquier alfabeto , definimos el oráculo aleatorio como un oráculo que devuelve elementos aleatorios de , de modo que cada elemento tiene la misma probabilidad de ser devuelto (por lo que la posibilidad de cada elemento es ).O Σ Σ 1ΣOΣΣ1|Σ|

Para algunos alfabetos y , posiblemente de diferentes tamaños, considere la clase de máquinas con acceso a . Estamos interesados ​​en las máquinas en esta clase que se comportan igual que . En otras palabras, queremos convertir un oráculo en un oráculo usando una máquina Turing. Llamaremos a esa máquina Turing un programa de conversión.Σ 2 O Σ 1 O Σ 2 O Σ 1 O Σ 2Σ1Σ2OΣ1OΣ2OΣ1OΣ2

Deje y . Convertir en un oráculo es fácil: consultamos dos veces, convirtiendo los resultados de la siguiente manera: , , , . Claramente, este programa se ejecuta en tiempo .Σ = { 0 , 1 , 2 , 3 } O Σ 1 O Σ 2 O Σ 1 00 0 01 1 10 2 11 3 O ( 1 )Σ1={0,1}Σ={0,1,2,3}OΣ1OΣ2OΣ1000011102113O(1)

Ahora dejemos y . Para estos dos idiomas, todos los programas de conversión se ejecutan en tiempo , es decir, no hay programas de conversión de a que se ejecutan en tiempo .Σ = { 0 , 1 , 2 } O ( ) O Σ 1 O Σ 2 O ( 1 )Σ1={0,1}Σ={0,1,2}O()OΣ1OΣ2O(1)

Esto se puede demostrar por contradicción: suponga que existe un programa de conversión de a ejecutándose en tiempo . Esto significa que hay un tal que realiza como máximo consultas a .O Σ 1 O Σ 2 O ( 1 ) d N C d Σ 1COΣ1OΣ2O(1)dNCdΣ1

d C C k C d - k CC puede hacer menos de consultas en ciertas rutas de ejecución. Podemos construir fácilmente un programa de conversión que ejecute , haciendo un seguimiento de cuántas veces se realizó una consulta Oracle. Sea el número de consultas de oráculo. luego hace consultas adicionales de oráculo, descartando los resultados, devolviendo lo que habría devuelto.dCCkCdkC

De esta manera, hay exactamente rutas de ejecución para . Exactamente de estas rutas de ejecución dará como resultado que devuelva . Sin embargo, no es un número entero, por lo que tenemos una contradicción. Por lo tanto, no existe tal programa.C 1|Σ1|d=2dC C02d1|Σ2|=13C02d3

De manera más general, si tenemos alfabetos y con y , entonces existe un programa de conversión de a si y sólo si todos los primos que aparecen en la factorización prima de también aparecen en la factorización prima de (por lo que los exponentes de los primos en la factorización no importan).Σ 2 | Σ 1 | = n | Σ 2 | = k O Σ 1 O Σ 2 n kΣ1Σ2|Σ1|=n|Σ2|=kOΣ1OΣ2nk

Una consecuencia de esto es que si tenemos un generador de números aleatorios que genera una cadena binaria de longitud , no podemos usar ese generador de números aleatorios para generar un número en con exactamente la misma probabilidad.{ 0 , 1 , 2 }l{0,1,2}

Pensé en el problema anterior cuando estaba parado en el supermercado, reflexionando sobre qué cenar. Me preguntaba si podría usar los lanzamientos de monedas para decidir entre las opciones A, B y C. Resulta que eso es imposible.

Alex ten Brink
fuente
55
La prueba de Dinur del teorema de PCP se basa en gran medida en la manipulación del tamaño del alfabeto, específicamente explotarlo y luego reducirlo a través de una composición de PCP repetidamente. Sin la segunda parte del paso (tirando hacia abajo del tamaño del alfabeto), la prueba no funciona.
Daniel Apon el
2
@Daniel Apon: ¿Por qué no volver a publicar como respuesta?
Joshua Grochow
@Joshua, oops. Por supuesto. :)
Daniel Apon el

Respuestas:

11

Hay algunos ejemplos en la teoría del lenguaje formal donde los alfabetos de 2 y 3 caracteres dan comportamientos cualitativamente diferentes. Kozen da el siguiente buen ejemplo (parafraseado):

Deje que el alfabeto sea = {1, .., k} con el orden numérico estándar, y defina sort (x) como la permutación de la palabra x en la que las letras de x aparecen en orden ordenado. Ampliar sort (A) = {sort (x) | x A}, y considere la siguiente afirmación:Σ

Si A no tiene contexto, entonces sort (A) no tiene contexto.

Esta afirmación es verdadera para k = 2, pero falsa para k 3.

mikero
fuente
11

La prueba de Dinur del teorema de PCP se basa en gran medida en la manipulación del tamaño del alfabeto.

Específicamente, la estructura general de la prueba es una aplicación iterativa de una técnica de potencia de gráfico un logaritmo en el número de veces que el tamaño del gráfico. En cada iteración, el gráfico se procesa previamente en un gráfico en expansión regular, amplificado por una potencia (que explota el tamaño del alfabeto), y luego se aplica una composición de PCP (convirtiendo cada restricción sobre un alfabeto grande en un sistema de restricciones sobre Un pequeño alfabeto).

El objetivo implícito del proceso es encontrar una manera de reutilizar el paso de amplificación hasta que el valor UNSAT se convierta en una fracción constante (lo que demuestra el teorema de PCP). El punto clave es que, a menos que el tamaño del alfabeto se retire cada vez, el gráfico resultante no es lo que se necesita para la reducción final.

Daniel Apon
fuente
9

O(1){0,1,2}

{0,1,2}{0,1}O(1) por Dodis, Patrascu y Thorup sobre él, y las referencias allí, deberían ser un buen punto de partida.

Matías
fuente
8

En los códigos de corrección de errores, es posible que haya una diferencia fundamental entre los códigos binarios y los códigos sobre alfabetos más grandes en que algunos creen que los ejemplos de Gilbert Varshamov para códigos que corrigen una fracción de errores (que son esencialmente ejemplos codiciosos o aleatorios) ser apretado en el caso binario y se sabe que no lo son sobre un alfabeto grande a través de códigos de geometría algebraica. Esto llevó a algunos a especular que la definición estándar de códigos de corrección de errores para un alfabeto grande no es el análogo correcto de los códigos de corrección de errores binarios.

Gil Kalai
fuente
5

3

El resultado es algo técnico, pero si está interesado, puede contrastar el Lema 8 con la Sección 4.1 para ver las afirmaciones relevantes del teorema.

Lev Reyzin
fuente
Esto parece muy interesante. ¿Has intentado modificar la definición de la influencia para ver si puedes obtener algo similar al caso booleano?
Kaveh
Nuestra definición de influencia es bastante natural: observa la distribución de probabilidad del nodo de salida dada la configuración diferente del objetivo. Si todos los ajustes producen la misma distribución de probabilidad exacta, entonces decimos que el objetivo no tiene influencia. En caso de que le interese, el modelo con el que trabajamos se llama modelo VIQ, que creo que es el modelo de aprendizaje de circuito más interesante. Fue definido en ( cs.yale.edu/homes/aspnes/… ) por Angluin et al. en STOC '06.
Lev Reyzin