Помощник преподавателя курса сумел написать программу, которая (детерминистически) генерирует сложные экзаменационные вопросы. Теперь она хотела бы написать программу, которая генерирует соответствующие ответы. Проблема Ревизора спрашивает, всегда ли это возможно; в ГИПОТЕЗА экзаменатора утверждает , что, если предположить, , это не : придумывают проблемы легче , чем придумывать свои решения.
Более формально: пусть - детерминированная машина Тьюринга, которая на входе генерирует за полиномиальное время булеву формулу размера . Я хотел бы знать , если для всех таких существует детерминированный полиномиальный времени машина Тьюринга , что на входе , выходы„ “ , если имеет удовлетворяющую назначение и" " в противном случае.1 n n M M ′ 1 n 1 M ( 1 n ) 0
Предполагая, что , этот вопрос уже был задан или получен ответ? Если нет ответа, какие дополнительные допущения ( например, односторонние функции?) Могут повлиять на результат? Если исключить любое из вышеперечисленного, моя «гипотеза» заключается в том, что «отвечающая» ТМ не всегда существует, но какова ваша интуиция?
Благодаря!
Ответы:
Вопрос, который вы задаете, эквивалентен унарному NP = унарному P, который, в свою очередь, эквивалентен NE = E путем заполнения.
Из заголовка, возможно, вы хотели спросить, можно ли сгенерировать пары ввода / вывода так, чтобы распределение на входах было «жестким». Возможность сделать это лежит где-то между P NP и односторонними функциями.≠
В ограниченных вычислительных моделях известно, что это возможно. Например, можно генерировать пары ввода / вывода для функций четности или большинства в AC 0 или ниже. См . Сложность дистрибутивов .0
источник
Вопрос: Пусть порождает формулы. Имеет ли { М ( 1 л ) | п ∈ N ∧ М ( 1 л ) ∈ S Т } принадлежат P ?M∈ P F { М( 1N) ∣ n ∈ N ∧ M( 1N) ∈ SА Т} п
Предположение о генерации формул за полиномиальное время от означает, что формула может быть кратко задана. Вы хотите определить их выполнимость во времени n O ( 1 ) .1N NO ( 1 )
Учитывая мы можем найти n за полиномиальное время в | φ | , Тогда φ можно сформулировать кратко в lg n + O ( 1 ) битах, используя M и n . Мы можем использовать наши S U с с я п т С ТОГО алгоритмом в Е , чтобы решить это во время - О ( Л.Г. п ) = п выводаφ = М( 1N) N | φ | φ Л.Г.n + O ( 1 ) M N ев у с с я п т SА Т Е .2O ( LGн )= nO ( 1 )
да :⟹s u c c i n c t SА ТЕ Е
Пусть й дан контур С в Унарном , М вычисляет строку сжатой формы , кодируемый C , и возвращает результат , если это формула и ⊥ в противном случае.M∈ P F С M С ⊥
Предположим , что принадлежат Р . Для решения S U с с я н гр т S A T запишем данную сжатую формулу в Унарный , а затем использовать наше предположение , чтобы решить эту проблему.{ М( 1N) ∣ n ∈ N ∧ M( 1N) ∈ SА Т} п s u c c i n c t SА Т
Вопрос: Можем ли мы генерировать в полиномиальном времени пары экземпляр-решение для , чтобы экземпляр был сложным?SА Т
Мы должны уточнить, что мы подразумеваем под тем, что экземпляр является сложным, так как любой экземпляр сам по себе (теоретически) прост, поскольку его можно решить с помощью алгоритма, который всегда говорит «да», или алгоритма, который всегда говорит «нет». Мне кажется, что вы пытались обойти эту проблему, навязывая единообразие. Думая в криптографических терминах, без какой-либо информации, которая не раскрывается злоумышленнику, нет смысла прятать остальную часть вычислений, поскольку злоумышленник может смоделировать протокол.
Предположим, что у нас есть алгоритм полиномиального времени, который генерирует пары экземпляр-решение. Противник может использовать тот же алгоритм, чтобы найти ответ, если он знает и найти n несложно по формуле. Более разумный способ - использовать случайно выбранный секретный ключ, чтобы обойти это и ослабить условие твердости, чтобы оно было вероятностным: ни один алгоритм за полиномиальное время не может найти решение с высокой вероятностью (без знания секретного ключа).N N
Или более формально,
Легко видеть, что такую функцию можно превратить в одностороннюю функцию, как если бы было легко найти из φ k, тогда мы можем найти ответ, вычислив A ( k ) 2 .К φК A ( k )2
С другой стороны, пусть - односторонняя функция. Мы можем выразить f ( x ) = y как схему полиномиального размера, так как f вычислима за полиномиальное время (и мы можем превратить ее в формулу, вводя новые переменные для всех вентилей и локально применяя условие для правильности вычисления как в переводе Цзяня). Рассмотрим y как параметр и обозначим полученную формулу как φ f , y ( x ) . Мы можем спросить, существует ли x, удовлетворяющий φ f , y ( x )е е( Х ) = у е Y φе, у( х ) Икс φе, у( х ) , Любой алгоритм за полиномиальное время, решающий эти экземпляры с пренебрежимо малой вероятностью, нарушит одностороннюю функцию f . Однако здесь используется тот факт, что противник должен найти свидетеля, а не только тот факт, что формула выполнима или нет (но я думаю, что мы можем обойти эту проблему, используя жесткую часть f ).SА Т е е
См. Также главы 29 и 30 книги Яна Крайчека «Форсирование со случайными переменными», 2011 год, о генераторах сложности доказательств .
источник