Exemplos em que o tamanho do alfabeto (

9

Vamos ser um alfabeto, ou seja, um não-vazio finito set. Uma string é qualquer sequência finita de elementos (caracteres) de Σ . Como exemplo, { 0 , 1 } é o alfabeto binário e 0110 é uma sequência para esse alfabeto.ΣΣ{0,1}0110

Normalmente, contanto que contenha mais de 1 elemento, o número exato de elementos em Σ não importa: na melhor das hipóteses, acabamos com uma constante diferente em algum lugar. Em outras palavras, realmente não importa se usamos o alfabeto binário, os números, o alfabeto latino ou Unicode.ΣΣ

Existem exemplos de situações em que importa o tamanho do alfabeto?

A razão pela qual estou interessado nisso é porque encontrei um exemplo:

Para qualquer alfabeto , definimos o oráculo aleatório O Σ como um oráculo que retorna elementos aleatórios de Σ , de modo que todo elemento tem uma chance igual de ser retornado (portanto, a chance para cada elemento é 1ΣOΣΣ)1|Σ|

Para alguns alfabetos e Σ 2 - possivelmente de tamanhos diferentes - considere a classe de máquinas oracle com acesso a O Σ 1 . Estamos interessados ​​nas máquinas oracle desta classe que se comportam da mesma forma que O Σ 2 . Em outras palavras, queremos converter um oráculo O Σ 1 em um oráculo O Σ 2 usando uma máquina de Turing. Vamos chamar essa máquina de Turing de programa de conversão.Σ1Σ2OΣ1OΣ2OΣ1OΣ2

Seja e Σ = { 0 , 1 , 2 , 3 } . Converter O Σ 1 em um oráculo O Σ 2 é fácil: consultamos O Σ 1 duas vezes, convertendo os resultados da seguinte forma: 00 0 , 01 1 , 10 2 , 11 3 . Claramente, este programa é executado em O (Σ1={0,1}Σ={0,1,2,3}OΣ1OΣ2OΣ1000011102113 hora.O(1)

Agora deixe e Σ = { 0 , 1 , 2 } . Para esses dois idiomas, todos os programas de conversão são executados no tempo O ( ) , ou seja, não há programas de conversão de O Σ 1 para O Σ 2 que são executados no tempo O ( 1 ) .Σ1={0,1}Σ={0,1,2}O()OΣ1OΣ2O(1)

Isso pode ser comprovado por contradição: suponha que exista um programa de conversão de O Σ 1 para O Σ 2 em execução no tempo O ( 1 ) . Isso significa que existe um d N tal que C faz no máximo d consultas para Σ 1 .COΣ1OΣ2O(1)dNCdΣ1

pode fazerconsultasmenos de d em certos caminhos de execução. Podemos facilmente construir um programa de conversão C ' que executa C , mantendo o controle de quantas vezes uma consulta oracle foi feita. Seja k o número de consultas do Oracle. C faz d - k consultas adicionais do oracle, descartando os resultados, retornando o que C teria retornado.CdCCkCdkC

Dessa forma, existem exatamente caminhos de execução para C . Exatamente 1|Σ1|d=2dC desses caminhos de execução resultarão emCretornando0. No entanto,2d1|Σ2|=13C0 não é um número inteiro, por isso temos uma contradição. Portanto, esse programa não existe.2d3

De maneira mais geral, se tivermos alfabetos e Σ 2 com | Σ 1 | = N e | Σ 2 | = k , existe um programa de conversão de O Σ 1 para O Σ 2 se e somente se todos os primos que aparecem na fatoração primária de n também aparecerem na fatoração primária de k (portanto, os expoentes dos primos na fatoração não não importa).Σ1Σ2|Σ1|=n|Σ2|=kOΣ1OΣ2nk

Uma conseqüência disso é que, se tivermos um gerador de números aleatórios gerando uma cadeia binária de comprimento , não podemos usar esse gerador de números aleatórios para gerar um número em { 0 , 1 , 2 } com probabilidade exatamente igual.l{0,1,2}

Pensei no problema acima quando estava no supermercado, pensando no que comer no jantar. Gostaria de saber se eu poderia usar o sorteio para decidir entre as opções A, B e C. Como se vê, isso é impossível.

Alex ten Brink
fonte
5
A prova de Dinur do teorema do PCP depende muito da manipulação do tamanho do alfabeto, especificamente explodindo-o e reduzindo-o através de uma composição de PCP repetidamente. Sem a segunda parte da etapa (puxando o tamanho do alfabeto de volta para baixo), a prova não funciona.
Daniel Daniel Apon
2
@ Daniel Apon: Por que não re-postar como resposta?
Joshua Grochow
@ Josué, oops. Certo. :)
Daniel Apon

Respostas:

11

Existem alguns exemplos na teoria formal da linguagem em que os alfabetos de 2 e 3 caracteres dão comportamentos qualitativamente diferentes. Kozen dá o seguinte exemplo (parafraseado):

Σ

Se A é livre de contexto, a classificação (A) é livre de contexto.

mikero
fonte
11

A prova de Dinur do teorema do PCP depende muito da manipulação do tamanho do alfabeto.

Especificamente, a estrutura geral da prova é uma aplicação iterativa de uma técnica de acionamento de gráfico, um logaritmo no número de vezes que o tamanho do gráfico é aplicado. Em cada iteração, o gráfico é pré-processado em um gráfico de expansão regular, amplificado por uma potência (que aumenta o tamanho do alfabeto) e, em seguida, é aplicada uma composição de PCP (transformando cada restrição em um alfabeto grande em um sistema de restrições). um pequeno alfabeto).

O objetivo implícito do processo é encontrar uma maneira de reutilizar a etapa de amplificação até que o valor UNSAT se torne uma fração constante (comprovando o teorema do PCP). O ponto principal é que, a menos que o tamanho do alfabeto seja recuado a cada vez, o gráfico resultante não é o necessário para a redução final.

Daniel Apon
fonte
9

O(1){0,1,2}

{0,1,2}{0,1}O(1) por Dodis, Patrascu e Thorup, e as referências nele, devem ser um bom ponto de partida.

Matthias
fonte
8

Nos códigos de correção de erros, é possível que exista uma diferença fundamental entre códigos binários e códigos em alfabetos maiores, pois alguns exemplos de Gilbert Varshamov para códigos que corrigem uma fração de erros (que são essencialmente exemplos gananciosos ou aleatórios) seja estanque no caso binário e sabe-se que não é estanque ao longo de um alfabeto grande por meio de códigos de geometria algébrica. Isso levou alguns a especular que a definição padrão de códigos de correção de erros para um alfabeto grande não é o análogo correto dos códigos de correção de erros binários.

Gil Kalai
fonte
5

3

O resultado é um pouco técnico, mas se você estiver interessado, pode contrastar o Lema 8 com a Seção 4.1 para obter as declarações relevantes do teorema.

Lev Reyzin
fonte
Isso parece muito interessante. Você já tentou modificar a definição da influência para ver se consegue algo semelhante ao caso booleano?
Kaveh
Nossa definição de influência é bastante natural - você olha para a distribuição de probabilidade do nó de saída, considerando diferentes configurações do destino. Se todas as configurações gerarem a mesma distribuição exata de probabilidade, dizemos que o alvo não tem influência. Caso você esteja interessado, o modelo em que trabalhamos é chamado de modelo VIQ, que eu acho que é o modelo de aprendizado de circuito mais interessante. Foi definido em ( cs.yale.edu/homes/aspnes/… ) por Angluin et al. no STOC '06.
Lev Reyzin