Мне любопытно, как вы видели неоднородность полезной в вычислениях. Одним из способов является случайность, как ви другой - это справочные таблицы, которые используются, чтобы показать, что все языки имеют неоднородные схемы.
В частности, меня интересуют способы использования объектов, о которых известно, что они существуют с помощью вероятностного метода и других неконструктивных (или недостаточно конструктивных) методов доказательства с использованием неравномерности. Я бы предпочел, чтобы примеры были естественными, а не надуманными. Чтобы было ясно, схема для надуманной проблемы может быть что-то вроде: учитывая некоторый языкЯ создаю схему полиномиального размера, вычисляя некоторые действительно сложные функции используя мой совет и спрашивая, ,
источник
Ответы:
Пример, который мне нравится, это аргументN E ⊆ c o N E / (n+1) путем подсчета строк на языке (см., например, https://blog.computationalcomplexity.org/2004/01/little-theorem.html ).
источник
Одним из примеров являетсяN L ⊆ U L / поли , Эта теорема была доказана Рейнхардтом и Аллендером в их работе «Делая недетерминированность однозначной» . Не вдаваясь в детали, совет в их алгоритме состоит из последовательности присваиваний веса ребра, так что для любого орграфаг кодируется N -битная строка, некоторое присваивание в последовательности делает г «мин-уникальный». Можно показать, что такая последовательность существует вероятностным методом. Основной вклад Рейнхардта и Аллендера состоял в том, чтобы дать однозначные алгоритмы лог-пространства для выяснения, какое назначение в последовательности работает для конкретного заданного орграфа.г и для принятия решения s -T связность на минимальном уникальном орграфе.
Как сB P P ⊆ P / поли Предполагается, что неоднородность здесь на самом деле не нужна, т. е. предполагается, что N L = U L ,
источник
Я не уверен, соответствует ли это тому, что вы ищете, но есть несколько результатов, доказывающих теоремы иерархии для классов семантической сложности с одним небольшим советом, где никакая теорема иерархии не известна без совета. Самый известный пример - BPP, для которого мы не знаем теорему об иерархии, но Fortnow и Santhanam показали, что она существует с одним небольшим советом (основываясь на результате Барака, который использовал больше советов). В этой статье Мелкебека и Первышева даются ссылки и история, а также теорема, которая, кажется, включает в себя предыдущие.
источник