Примеры, в которых размер алфавита (

9

Позволять Σбыть алфавитом, то есть непустым конечным множеством. Строка - это любая конечная последовательность элементов (символов) изΣ, Например,{0,1} это двоичный алфавит и 0110 это строка для этого алфавита.

Обычно, пока Σ содержит более 1 элемента, точное количество элементов в Σне имеет значения: в лучшем случае мы получаем где-то другую константу. Другими словами, не имеет значения, используем ли мы двоичный алфавит, цифры, латинский алфавит или Unicode.

Есть ли примеры ситуаций, в которых важно, насколько велик алфавит?

Я заинтересован в этом потому, что случайно наткнулся на один такой пример:

Для любого алфавита Σ мы определяем случайный оракул OΣ быть оракулом, который возвращает случайные элементы из Σтак, что каждый элемент имеет равную вероятность быть возвращенным (таким образом, шанс для каждого элемента 1|Σ|).

Для некоторых алфавитов Σ1 а также Σ2 - возможно разных размеров - рассмотрим класс оракулов с доступом к OΣ1, Мы заинтересованы в машинах оракула этого класса, которые ведут себя так же, какOΣ2, Другими словами, мы хотим обратить оракулаOΣ1 в оракула OΣ2используя машину Тьюринга. Мы назовем такую ​​машину Тьюринга программой преобразования.

Позволять Σ1={0,1} а также Σ={0,1,2,3}, преобразованиеOΣ1 в оракула OΣ2 это просто: мы запрашиваем OΣ1 дважды, конвертируя результаты следующим образом: 000, 011, 102, 113, Понятно, что эта программа работает вO(1) время.

Теперь давай Σ1={0,1} а также Σ={0,1,2}, Для этих двух языков все конверсионные программы работают вO() время, то есть нет программ конвертации из OΣ1 в OΣ2 которые бегут в O(1) время.

Это может быть доказано противоречием: предположим, что существует конверсионная программа C от OΣ1 в OΣ2 работает в O(1)время. Это означает, что естьdN такой, что C делает максимум d запросы к Σ1,

C может сделать меньше чем dзапросы в определенных путях выполнения. Мы можем легко построить программу конвертацииC который выполняет C, отслеживая, сколько раз был сделан запрос оракула. Позволятьk быть число оракулов. C затем делает dk дополнительные запросы оракула, отбрасывая результаты, возвращая то, что C вернулся бы.

Таким образом, есть именно |Σ1|d=2d пути выполнения для C, Точно1|Σ2|=13 из этих путей выполнения приведет к C возврате 0, Однако,2d3не является целым числом, поэтому у нас есть противоречие. Следовательно, такой программы не существует.

В целом, если у нас есть алфавиты Σ1 а также Σ2 с |Σ1|=n а также |Σ2|=kтогда существует программа преобразования из OΣ1 в OΣ2 тогда и только тогда, когда все простые числа появляются в главном разложении n также появляются в основной факторизации k (так что показатели простых чисел при факторизации не имеют значения).

Следствием этого является то, что если у нас есть генератор случайных чисел, генерирующий двоичную строку длины lмы не можем использовать этот генератор случайных чисел для генерации числа в {0,1,2} с точно равной вероятностью.

Я придумал вышеупомянутую проблему, стоя в супермаркете, размышляя, что есть на ужин. Я задавался вопросом, могу ли я использовать броски монет, чтобы выбрать между выбором A, B и C. Как оказалось, это невозможно.

Алекс тен Бринк
источник
5
Доказательство Динуром теоремы PCP в значительной степени основано на манипулировании размером алфавита, в частности, взрыва его и последующего многократного уменьшения с помощью композиции PCP. Без второй части шага (перенесение размера алфавита обратно) доказательство не сработает.
Даниэль Апон
2
@ Даниэль Апон: Почему бы не опубликовать в качестве ответа?
Джошуа Грохов
@ Джошуа, ой. Конечно. :)
Даниэль Апон

Ответы:

11

В теории формального языка есть несколько примеров, когда двухбуквенный и трехбуквенный алфавиты дают качественно различное поведение. Козен приводит следующий хороший пример (перефразированный):

Пусть алфавит будет Σ= {1, .., k} со стандартным числовым порядком и определите sort (x) как перестановку слова x, в котором буквы x появляются в отсортированном порядке. Расширить sort (A) = {sort (x) | Икс A} и рассмотрите следующую претензию:

Если A не зависит от контекста, то sort (A) не зависит от контекста.

Это утверждение верно для k = 2, но неверно для k 3.

mikero
источник
11

Доказательство Динуром теоремы PCP в значительной степени основано на манипуляции размером алфавита

В частности, общая структура доказательства представляет собой итеративное применение метода питания графов - логарифм по размеру графа количество раз. На каждой итерации график предварительно обрабатывается в регулярный расширяющийся граф, усиливается степенью (которая увеличивает размер алфавита), а затем применяется композиция PCP (превращающая каждое ограничение большого алфавита в систему ограничений над маленький алфавит).

Неявная цель этого процесса состоит в том, чтобы найти способ повторно использовать этап амплификации, пока значение UNSAT не станет постоянной величиной (доказательство теоремы PCP). Ключевым моментом является то, что, если размер алфавита не возвращается каждый раз, результирующий график не является тем, что необходимо для окончательного сокращения.

Даниэль Апон
источник
9

Требования вашего примера довольно строгие. Если вы расслабитесь, чтобы только потребовать, чтобы преобразование работало вO(1)в ожидании . Можно сэмплировать равномерно из{0,1,2} используя, в ожидании, постоянное количество подбрасываний монет.

Я не эксперт в этом, но один хороший пример, где размер алфавита имеет значение, это кодирование и сжатые структуры данных. Представьте, что вы хотите представить сообщение по алфавиту{0,1,2} в алфавите {0,1}(например, чтобы сохранить его в вашем двоичном компьютере). Вы хотите минимизировать требуемое пространство, но в то же время хотите иметь возможность быстро читать и писать отдельные символы сообщения (скажем, вO(1)). Подобные проблемы изучались довольно давно. Хорошая отправная точка должна послужить недавней работе Додиса, Патраску и Торупа, а также ссылкам в ней.

Матиас
источник
8

В кодах с исправлением ошибок возможно, что есть принципиальное различие между двоичными кодами и кодами над большими алфавитами в том, что некоторые примеры Гилберта Варшамова для кодов, которые исправляют часть ошибок (которые по существу являются жадными или случайными примерами), считаются некоторыми быть стесненным в двоичном случае и, как известно, не стесняться в большом алфавите с помощью кодов алгебраической геометрии. Это побудило некоторых предположить, что стандартное определение кодов с исправлением ошибок для большого алфавита не является правильным аналогом двоичных кодов с исправлением ошибок.

Гил Калай
источник
5

В моем собственном исследовании небольших различий в размерах алфавита я столкнулся с интересным случаем, который привел к существенным различиям в получившейся теории. Грубое описание проблемы обучения вероятностных схем состоит в следующем: ученик может переопределять ворота скрытой цепи и наблюдать полученный вывод, а цель состоит в том, чтобы произвести «функционально эквивалентную» цепь. Для логических цепей всякий раз, когда затвор имеет «влияние» на выход, можно изолировать влиятельный путь от этого затвора до выхода схемы. Для цепей алфавита размером3это больше не имеет место - а именно, есть схемы, которые имеют затворы, которые имеют большое влияние на выходное значение, но не влияют на какой-либо один путь к выходу! Мы нашли этот результат довольно удивительным.

Результат несколько технический, но если вам интересно, вы можете сопоставить лемму 8 с разделом 4.1 для соответствующих утверждений теоремы.

Лев Рейзин
источник
Это кажется очень интересным. Вы пытались изменить определение влияния, чтобы посмотреть, сможете ли вы получить что-то похожее на логический случай?
Каве
Наше определение влияния довольно естественное - вы смотрите на распределение вероятностей выходного узла при разных настройках цели. Если все настройки дают одинаковое точное распределение вероятностей, то мы говорим, что цель не имеет влияния. Если вам интересно, модель, над которой мы работали, называется моделью VIQ, которая, я думаю, является самой интересной моделью схемного обучения. Это было определено в ( cs.yale.edu/homes/aspnes/… ) Angluin et al. в STOC '06.
Лев Рейзин