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.
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)
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.
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 ( hora.
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 ) .
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 .
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.
Dessa forma, existem exatamente caminhos de execução para C ′ . Exatamente 1 desses caminhos de execução resultarão emC′retornando0. No entanto,2d não é um número inteiro, por isso temos uma contradição. Portanto, esse programa não existe.
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).
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.
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.
Respostas:
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):
fonte
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.
fonte
fonte
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.
fonte
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.
fonte