Какие примеры того, как может быть полезна неоднородность?

9

Мне любопытно, как вы видели неоднородность полезной в вычислениях. Одним из способов является случайность, как вВппп/поLYи другой - это справочные таблицы, которые используются, чтобы показать, что все языки имеют неоднородные схемы.

В частности, меня интересуют способы использования объектов, о которых известно, что они существуют с помощью вероятностного метода и других неконструктивных (или недостаточно конструктивных) методов доказательства с использованием неравномерности. Я бы предпочел, чтобы примеры были естественными, а не надуманными. Чтобы было ясно, схема для надуманной проблемы может быть что-то вроде: учитывая некоторый языкLпЯ создаю схему полиномиального размера, вычисляя некоторые действительно сложные функции е(|Икс|) используя мой совет и спрашивая, е(|Икс|)N/|е(|Икс|)|ИксL,

Сэмюэль Шлезингер
источник
Таким образом, под «полезным» я предполагаю, что вы имеете в виду значительное уменьшение ресурсов, необходимых для решения проблемы? например, неоднородные схемы, которые значительно меньше однородных, или машины Тьюринга с рекомендациями, которые работают гораздо быстрее, чем без рекомендаций?
Усул
Это эквивалентно, нет? Я действительно имел в виду полезное, как в «привыкли доказывать что-то интересное», однако
Сэмюэль Шлезингер
Думаю, я бы предположил, что все интересные вещи, которые вы докажете, используя неравномерность, в основном попадут в то, что вы говорите, за исключением того, что, возможно, схемы будут лучше, чем известные однородные, но не лучше, чем возможные,
Сэмюэль Шлезингер,

Ответы:

11

Пример, который мне нравится, это аргумент NЕсоNЕ/(N+1)путем подсчета строк на языке (см., например, https://blog.computationalcomplexity.org/2004/01/little-theorem.html ).

Эмиль Йержабек
источник
Это здорово, потому что он не опирается на вероятностный метод или справочные таблицы. Спасибо за это.
Сэмюэль Шлезингер
(Обратите внимание, что если длина строки подсказки должна быть точной, то Nне совсем очевидно , работа (и я не вижу какой - либо способ , чтобы показать , что она работает, очевидно, ни-нет)).
Я думаю, что классы советов обычно не определены, чтобы иметь точную длину советов @RickyDemer
Сэмюэль Шлезингер
Кроме того, я пока не вижу этого в своих попытках, поэтому, если бы кто-то мог дать ссылку или упомянуть, как это увидеть, я был бы признателен
Самуэль Шлезингер,
1
@SamuelSchlesinger: в то время как P / poly или C / log (для любого класса C) обычно определяются с длиной совета до большой-О, это не всегда так. В некоторых результатах используется точное количество битов рекомендаций (иногда до 1!).
Джошуа Грохов
10

Одним из примеров является NLUL/поли, Эта теорема была доказана Рейнхардтом и Аллендером в их работе «Делая недетерминированность однозначной» . Не вдаваясь в детали, совет в их алгоритме состоит из последовательности присваиваний веса ребра, так что для любого орграфаг кодируется N-битная строка, некоторое присваивание в последовательности делает г«мин-уникальный». Можно показать, что такая последовательность существует вероятностным методом. Основной вклад Рейнхардта и Аллендера состоял в том, чтобы дать однозначные алгоритмы лог-пространства для выяснения, какое назначение в последовательности работает для конкретного заданного орграфа.г и для принятия решения s-T связность на минимальном уникальном орграфе.

Как с Вппп/полиПредполагается, что неоднородность здесь на самом деле не нужна, т. е. предполагается, что NLзнак равноUL,

Уильям Хоза
источник
6

Я не уверен, соответствует ли это тому, что вы ищете, но есть несколько результатов, доказывающих теоремы иерархии для классов семантической сложности с одним небольшим советом, где никакая теорема иерархии не известна без совета. Самый известный пример - BPP, для которого мы не знаем теорему об иерархии, но Fortnow и Santhanam показали, что она существует с одним небольшим советом (основываясь на результате Барака, который использовал больше советов). В этой статье Мелкебека и Первышева даются ссылки и история, а также теорема, которая, кажется, включает в себя предыдущие.

Сашо Николов
источник
Если это только один бит, мы не можем просто перебрать его, как в случае п/Lог?
Т ....
@ Turbo Является ли ваше утверждение, что BPP / 1 совпадает с BPP. Попробуйте записать доказательство, и вы сможете легко увидеть, где это не так
Сашо Николов