Проблема экзаменатора (единообразная генерация SAT-решений / ответов)

11

Помощник преподавателя курса сумел написать программу, которая (детерминистически) генерирует сложные экзаменационные вопросы. Теперь она хотела бы написать программу, которая генерирует соответствующие ответы. Проблема Ревизора спрашивает, всегда ли это возможно; в ГИПОТЕЗА экзаменатора утверждает , что, если предположить, , это не : придумывают проблемы легче , чем придумывать свои решения.PNP

Более формально: пусть - детерминированная машина Тьюринга, которая на входе генерирует за полиномиальное время булеву формулу размера . Я хотел бы знать , если для всех таких существует детерминированный полиномиальный времени машина Тьюринга , что на входе , выходы„ “ , если имеет удовлетворяющую назначение и" " в противном случае.1 n n M M 1 n 1 M ( 1 n ) 0M1nnMM1n1M(1n)0

Предполагая, что , этот вопрос уже был задан или получен ответ? Если нет ответа, какие дополнительные допущения ( например, односторонние функции?) Могут повлиять на результат? Если исключить любое из вышеперечисленного, моя «гипотеза» заключается в том, что «отвечающая» ТМ не всегда существует, но какова ваша интуиция?PNP

Благодаря!

усул
источник
Позвольте мне убедиться, что у меня есть правильные квантификаторы. Вы спрашиваете, правда ли, что «для всех существует M , такой, что M может эффективно решить вывод M », верно? MMMM
Тайсон Уильямс
@TysonWilliams: Да, я немного отредактировал формулировку, чтобы попытаться прояснить это. Ваше заявление должно быть, я думаю, эквивалентно моему!
usul
1
Как указывает Эмануэле, это, вероятно, не то, что вы на самом деле ищете, вы, вероятно, захотите сгенерировать пары «экземпляр-решение», где решение экземпляра «сложно». Возможно, связано с тем, что вы ищете: 1. ответ Дэвида здесь и 2. раздел 6 Стивена А. Кука и Дэвида Дж. Митчелла, « Поиск трудных примеров проблемы удовлетворенности: обзор », 1997
Каве

Ответы:

12

Вопрос, который вы задаете, эквивалентен унарному NP = унарному P, который, в свою очередь, эквивалентен NE = E путем заполнения.

Из заголовка, возможно, вы хотели спросить, можно ли сгенерировать пары ввода / вывода так, чтобы распределение на входах было «жестким». Возможность сделать это лежит где-то между P NP и односторонними функциями.

В ограниченных вычислительных моделях известно, что это возможно. Например, можно генерировать пары ввода / вывода для функций четности или большинства в AC 0 или ниже. См . Сложность дистрибутивов .0

Manu
источник
1
Можете ли вы объяснить, почему это эквивалентно? ... Под «униформой» я подразумеваю «унифицированную модель вычислений» - если бы мы задали вопрос для схем, ответ был бы тривиально да : каждый жестко закодировал бы либо единицу, либо ноль, в зависимости от того, является ли M п выполнимо или нет. MnMn
usul
4
Каждый дает язык подсчета в NP: L M = { 1 n : M ( 1 n )  выполнимо. } . Так что если унарный-NP равно одноместной-Р, то М ' является машина , которая решает L M . В другом направлении, возьмите любой язык подсчета в NP и возьмите M в качестве машины, которая переводит его в SAT. Если M существует, то язык подсчета также находится в P, поэтому унарный P = унарный NP. Для второй эквивалентности вы можете проверить Hartmanis et al. (но одно направление очень легко) dl.acm.org/citation.cfm?id=808769MLM={1n:M(1n) is satisfiable.}MLMMM
Сашо Николов
4

Вопрос: Пусть порождает формулы. Имеет ли { М ( 1 л ) | п NМ ( 1 л ) S Т } принадлежат P ?MPF{M(1n)nNM(1n)SAT}P

succinctSATE Да:

Предположение о генерации формул за полиномиальное время от означает, что формула может быть кратко задана. Вы хотите определить их выполнимость во времени n O ( 1 ) .1nnO(1)

Учитывая мы можем найти n за полиномиальное время в | φ | , Тогда φ можно сформулировать кратко в lg n + O ( 1 ) битах, используя M и n . Мы можем использовать наши S U с с я п т С ТОГО алгоритмом в Е , чтобы решить это во время - О ( Л.Г. п ) = п выводаφ=M(1n)n|φ|φlgn+O(1)MnsuccintSATE .2O(lgn)=nO(1)

да :sUссяNсTSATЕ

Пусть й дан контур С в Унарном , М вычисляет строку сжатой формы , кодируемый C , и возвращает результат , если это формула и в противном случае.MпFСMС

Предположим , что принадлежат Р . Для решения S U с с я н гр т S A T запишем данную сжатую формулу в Унарный , а затем использовать наше предположение , чтобы решить эту проблему.{M(1N)|NNM(1N)SAT}пsUссяNсTSAT

Вопрос: Можем ли мы генерировать в полиномиальном времени пары экземпляр-решение для , чтобы экземпляр был сложным?SAT

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

Предположим, что у нас есть алгоритм полиномиального времени, который генерирует пары экземпляр-решение. Противник может использовать тот же алгоритм, чтобы найти ответ, если он знает и найти n несложно по формуле. Более разумный способ - использовать случайно выбранный секретный ключ, чтобы обойти это и ослабить условие твердости, чтобы оно было вероятностным: ни один алгоритм за полиномиальное время не может найти решение с высокой вероятностью (без знания секретного ключа).NN

Существует ли эффективные (детерминированный) алгоритм таким образом, что дано случайно выбранный к { 0 , 1 } п , генерирует пару из SAT экземпляры ф к и его ответу ш к таким образом, что не эффективно (вероятностный / неоднородный) алгоритм состязательного D можно правильно решить SAT-экземпляры, сгенерированные A, с ничтожной вероятностью?A
К{0,1}N
φКвесК
D
A

Или более формально,

Существует ли такой, что для всех D P / p o l y , такой, что S A T ( A ( k ) 1 ) = A ( k ) 2 для всех k и P r k { 0 , 1 } n { D ( A ( k ) 1 ) = S A TAпFDп/поLYSAT(A(К)1)знак равноA(К)2К

прК{0,1}N{D(A(К)1)знак равноSAT(A(К)1)}<1поLY(N)

Легко видеть, что такую ​​функцию можно превратить в одностороннюю функцию, как если бы было легко найти из φ k, тогда мы можем найти ответ, вычислив A ( k ) 2 .КφКA(К)2

С другой стороны, пусть - односторонняя функция. Мы можем выразить f ( x ) = y как схему полиномиального размера, так как f вычислима за полиномиальное время (и мы можем превратить ее в формулу, вводя новые переменные для всех вентилей и локально применяя условие для правильности вычисления как в переводе Цзяня). Рассмотрим y как параметр и обозначим полученную формулу как φ f , y ( x ) . Мы можем спросить, существует ли x, удовлетворяющий φ f , y ( x )ее(Икс)знак равноYеYφе,Y(Икс)Иксφе,Y(Икс), Любой алгоритм за полиномиальное время, решающий эти экземпляры с пренебрежимо малой вероятностью, нарушит одностороннюю функцию f . Однако здесь используется тот факт, что противник должен найти свидетеля, а не только тот факт, что формула выполнима или нет (но я думаю, что мы можем обойти эту проблему, используя жесткую часть f ).SATее

См. Также главы 29 и 30 книги Яна Крайчека «Форсирование со случайными переменными», 2011 год, о генераторах сложности доказательств .

Кава
источник
M'