Exemples dans lesquels la taille de l'alphabet (

9

Soit un alphabet, c'est-à-dire un ensemble fini non vide. Une chaîne est une séquence finie d'éléments (caractères) de Σ . Par exemple, { 0 , 1 } est l'alphabet binaire et 0110 est une chaîne pour cet alphabet.ΣΣ{0,1}0110

Habituellement, tant que contient plus d'un élément, le nombre exact d'éléments dans Σ n'a pas d'importance: au mieux, nous nous retrouvons quelque part avec une constante différente. En d'autres termes, peu importe si nous utilisons l'alphabet binaire, les chiffres, l'alphabet latin ou Unicode.ΣΣ

Existe-t-il des exemples de situations dans lesquelles la taille de l'alphabet est importante?

La raison pour laquelle cela m'intéresse, c'est parce que je suis tombé sur un exemple:

Pour tout alphabet nous définissons l'oracle aléatoire O Σ comme un oracle qui renvoie des éléments aléatoires de Σ , de sorte que chaque élément a une chance égale d'être retourné (donc la chance pour chaque élément est 1ΣOΣΣ).1|Σ|

Pour certains alphabets et Σ 2 - éventuellement de tailles différentes - considérez la classe des machines oracle ayant accès à O Σ 1 . Nous nous intéressons aux machines oracle de cette classe qui se comportent de la même manière que O ΣΣ1Σ2OΣ1 . En d'autres termes, nous voulons convertir un oracleO Σ 1 en un oracleO Σ 2 à l' aide d'une machine de Turing. Nous appellerons une telle machine de Turing un programme de conversion.OΣ2OΣ1OΣ2

Soit et Σ = { 0 , 1 , 2 , 3 } . Convertir O Σ 1 en oracle O Σ 2 est simple: on interroge O Σ 1 deux fois, en convertissant les résultats comme suit: 00 0 ,Σ1={0,1}Σ={0,1,2,3}OΣ1OΣ2OΣ1000 , 10 2 , 11 3 . De toute évidence, ce programme s'exécute en O (011dix2113 temps.O(1)

Soit maintenant et Σ = { 0 , 1 , 2 } . Pour ces deux langues, tous les programmes de conversion s'exécutent en temps O ( ) , c'est-à-dire qu'il n'y a pas de programme de conversion depuis O Σ 1Σ1={0,1}Σ={0,1,2}O()OΣ1 à qui s'exécute en temps O ( 1 ) .OΣ2O(1)

Cela peut être prouvé par contradiction: supposons qu'il existe un programme de conversion de O Σ 1 en O Σ 2 fonctionnant en temps O ( 1 ) . Cela signifie qu'il y a un dCOΣ1OΣ2O(1) tel que C effectue au plus d requêtes à Σ 1 .NCΣ1

peut effectuer moins de d requêtes dans certains chemins d'exécution. Nous pouvons facilement construire un programme de conversion C ' qui exécute C , en gardant une trace du nombre de fois qu'une requête Oracle a été faite. Soit k le nombre de requêtes oracle. C effectue ensuite d - k requêtes oracle supplémentaires, rejetant les résultats, renvoyant ce que C aurait retourné.CCCkC-kC

De cette façon, il y a exactement chemins d'exécution pour C . Exactement 1|Σ1|=2C de ces chemins d'exécution se traduiront parleretourparC'de0. Cependant,2jours1|Σ2|=13C0 n'est pas un nombre entier, nous avons donc une contradiction. Par conséquent, aucun programme de ce type n'existe.23

Plus généralement, si nous avons les alphabets et Σ 2 avec | Σ 1 | = n et | Σ 2 | = k , alors il existe un programme de conversion de O Σ 1 enΣ1Σ2|Σ1|=n|Σ2|=kOΣ1 si et seulement si tous les nombres premiers apparaissant dans la factorisation première de n apparaissent également dans la factorisation prime de k (donc les exposants des nombres premiers dans la factorisation ne font pas importe pas).OΣ2nk

Une conséquence de ceci est que si nous avons un générateur de nombres aléatoires générant une chaîne binaire de longueur , nous ne pouvons pas utiliser ce générateur de nombres aléatoires pour générer un nombre dans { 0 , 1 , 2 } avec une probabilité exactement égale.l{0,1,2}

J'ai pensé au problème ci-dessus en me tenant au supermarché, en réfléchissant à ce que j'aurais à dîner. Je me demandais si je pouvais utiliser des lancers de pièces pour décider entre les choix A, B et C. En fait, c'est impossible.

Alex ten Brink
la source
5
La preuve de Dinur du théorème du PCP repose fortement sur la manipulation de la taille de l'alphabet, en le faisant exploser puis en le réduisant via une composition PCP à plusieurs reprises. Sans la deuxième partie de l'étape (en tirant la taille de l'alphabet vers le bas), la preuve ne fonctionne pas.
Daniel Apon
2
@Daniel Apon: Pourquoi ne pas republier comme réponse?
Joshua Grochow
@Joshua, oups. Sûr. :)
Daniel Apon

Réponses:

11

Il existe quelques exemples dans la théorie du langage formel où les alphabets à 2 et 3 caractères donnent des comportements qualitativement différents. Kozen donne le bel exemple suivant (paraphrasé):

Soit l'alphabet = {1, .., k} avec l'ordre numérique standard, et définissez sort (x) comme la permutation du mot x dans lequel les lettres de x apparaissent dans l'ordre trié. Étendre le tri (A) = {sort (x) | x A}, et considérons la revendication suivante:Σ

Si A est hors contexte, alors sort (A) est hors contexte.

Cette affirmation est vraie pour k = 2, mais fausse pour k 3.

mikero
la source
11

La preuve de Dinur du théorème du PCP repose fortement sur la manipulation de la taille de l'alphabet.

Plus précisément, la structure globale de la preuve est une application itérative d'une technique d'alimentation de graphe un logarithme dans le nombre de fois de taille de graphe. À chaque itération, le graphique est prétraité en un graphique à expansion régulière, amplifié par une puissance (qui fait exploser la taille de l'alphabet), puis une composition PCP est appliquée (transformant chaque contrainte d'un grand alphabet en un système de contraintes sur un petit alphabet).

L'objectif implicite du processus est de trouver un moyen de réutiliser l'étape d'amplification jusqu'à ce que la valeur UNSAT devienne une fraction constante (prouvant le théorème du PCP). Le point clé est qu'à moins que la taille de l'alphabet ne soit retirée à chaque fois, le graphique résultant n'est pas ce qui est nécessaire pour la réduction finale.

Daniel Apon
la source
9

Les exigences de votre exemple sont assez strictes. Si vous le relâchez pour exiger uniquement que la conversion fonctionne dans dans l' attente . Il est possible d'échantillonner uniformément à partir de { 0 , 1 , 2 }O(1){0,1,2} utilisant, dans l'attente, un nombre constant de lancers de pièces.

Je ne suis pas un expert en la matière, mais un bel exemple où la taille de l'alphabet importe est le codage et les structures de données succinctes. Imaginez que vous souhaitez représenter un message sur l'alphabet dans l'alphabet { 0 , 1 } (par exemple pour le stocker dans votre ordinateur binaire). Vous voulez minimiser l'espace requis mais en même temps, vous voulez pouvoir lire et écrire rapidement les caractères individuels du message (disons dans O ( 1 ) ). De tels problèmes sont étudiés depuis un certain temps maintenant. L' article récent{0,1,2}{0,1}O(1) par Dodis, Patrascu et Thorup à ce sujet, et les références qui y figurent, devraient être un bon point de départ.

Matthias
la source
8

Dans les codes de correction d'erreurs, il est possible qu'il existe une différence fondamentale entre les codes binaires et les codes sur des alphabets plus grands en ce que certains pensent que les exemples de Gilbert Varshamov pour les codes qui corrigent une fraction des erreurs (qui sont essentiellement des exemples gourmands ou aléatoires) être serré dans le cas binaire et sont connus pour ne pas être serrés sur un grand alphabet via des codes de géométrie algébrique. Cela a conduit certains à spéculer que la définition standard des codes de correction d'erreur pour un grand alphabet n'est pas le bon analogue des codes de correction d'erreur binaire.

Gil Kalai
la source
5

J'ai rencontré un cas intéressant dans ma propre recherche de petites différences dans la taille de l'alphabet faisant des différences dramatiques dans la théorie résultante. Une description approximative du problème de l'apprentissage des circuits probabilistes est la suivante: un apprenant peut passer outre les portes d'un circuit caché et observer la sortie résultante, et l'objectif est de produire un circuit "fonctionnellement équivalent". Pour les circuits booléens, chaque fois qu'une porte a une "influence" sur la sortie, on peut isoler un chemin influent de cette porte vers la sortie du circuit. Pour les circuits de taille alphabétique cela ne devient plus le cas - à savoir, il y a des circuits qui ont des portes avec une grande influence sur la valeur de sortie, mais aucune influence le long d'un seul chemin vers la sortie!3

Le résultat est quelque peu technique, mais si vous êtes intéressé, vous pouvez comparer le lemme 8 avec la section 4.1 pour les déclarations pertinentes du théorème.

Lev Reyzin
la source
Cela semble très intéressant. Avez-vous essayé de modifier la définition de l'influence pour voir si vous pouvez obtenir quelque chose de similaire au cas booléen?
Kaveh
Notre définition de l'influence est assez naturelle - vous regardez la distribution de probabilité du nœud de sortie en fonction des différents paramètres de la cible. Si tous les paramètres donnent la même distribution de probabilité exacte, alors nous disons que la cible n'a aucune influence. Si vous êtes intéressé, le modèle sur lequel nous avons travaillé s'appelle le modèle VIQ, qui, je pense, est le modèle d'apprentissage de circuit le plus intéressant. Il a été défini dans ( cs.yale.edu/homes/aspnes/… ) par Angluin et al. dans STOC '06.
Lev Reyzin