Функция, которая гарантированно будет односторонней, если существуют односторонние функции?

Существует старая хитрость для записи алгоритма, который, если P = NP, решает SAT за полиномиальное время. По сути, каждый перечисляет все полиномиальные машины времени и многозадачность над ними.

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

Кажется, нет простого способа имитировать трюк P = NP. В этом случае мы можем быстро распознать решение, когда оно у нас есть. Но если я выполняю многозадачность для всех полиномиальных функций времени, нет очевидного способа распознать одностороннюю функцию, когда я прибуду к ней.

Если ответ на поставленный выше вопрос - нет, есть ли какой-то аргумент, почему мы не можем этого сделать? Может быть, запись такой функции как-то докажет, что существуют односторонние функции?

universal-computation one-way-function Тимоти Чоу
источник

Привет Тимоти Чоу, может быть, вы можете помочь и указать ссылку, где форма для записи алгоритма, что, если P = NP, решает SAT за полиномиальное время, формализован? Огромное спасибо

Ави Тал

@AviTal Смотрите, например, это: scholarpedia.org/article/Universal_search

Ванесса

Ответы:

Да, такую функцию нашел сам Левин, опубликованный несколько недавно:

Повесть об односторонних функциях . Проблемы передачи информации (= Проблемы передачи информации), 39 (1): 92-103, 2003.

Бьёрн Кьос-Хансен
источник

Благодарность! Используя Google Scholar, я смог использовать эту ссылку, чтобы найти ссылку на полную криптосистему с открытым ключом, авторы Григорьев, Хирш и Первышев, Groups-Complexity-Cryptology 1 (2009), 1-12.

Тимоти Чоу

Не могли бы вы объяснить детали этой функции? Что и почему он прерывается после n ^ 2 шагов, почему «сохранить копию префикса программы и принудительно установить ее, а также длину ввода на выходе» и что «только в местах, где такое возможное расширение является уникальным», означает точно , Я не знаю, заслуживает ли это отдельного вопроса.

Галмейда

@ BjørnKjos-Hanssen cstheory.stackexchange.com/questions/44496/…

galmeida