Существуют ли какие-либо классы функций, для которых требуются доказуемо разные ресурсы для вычислений, а не для вычисления их обратных?

Заранее извиняюсь, если этот вопрос слишком прост.

По сути, я хочу знать, есть ли какие-либо функции со следующими свойствами: $f(x)$

Возьмем как когда домен и кодомен ограничены битными строками. потом $f_n(x)$ $f(x)$ $n$

$f_n(x)$ инъективен
$f_n(x)$ сюръективен
$f_n(x)$ требует строго меньше ресурсов (либо пространство / время / глубина контура / количество вентилей) для вычисления по некоторой разумной модели, чем , где . $f^{-1}_n(y)$ $y=f_n(x)$
Разница в ресурсах для $f_n(x)$ против $f^{-1}(y)$ масштабируется как некоторая строго возрастающая функция $n$ .

Я могу привести примеры, когда функция является либо сюръективной, либо инъективной, но не обоими, если только я не прибегаю к надуманной вычислительной модели. Если я выберу вычислительную модель, которая допускает сдвиги влево в единицу времени на каком-то кольце, но не сдвиги вправо, то, конечно, можно придумать линейную надстройку (или выше, если вы рассматриваете более сложную перестановку как примитив) , По этой причине меня интересуют только разумные модели, под которыми я в основном имею в виду машины Тьюринга, схемы NAND или аналогичные.

Очевидно, что это должно быть верно, если $P\neq NP$ , но может показаться, что это также возможно, если $P=NP$ , и поэтому не должно равняться решению этого вопроса.

Вполне возможно, что этот вопрос имеет очевидный ответ или явное препятствие для ответа, который я пропустил.

cc.complexity-theory Джо Фитцсимонс
источник

Это не та область, которую я хорошо понимаю, но кажется, что вы ищете перестановку из n битов, которую трудно инвертировать. Я помню, как читал в газете Hastad ( nada.kth.se/~johanh/onewaync0.ps ), что существуют перестановки, которые есть в , но которые P-трудно инвертировать.

N C^{0}

$NC^0$

Робин Котари

См. Также ссылки на предыдущую работу в газете Хостада 1987 года. В нем упоминается, что Boppana и Lagarias (1986) приводят пример перестановки, которая находится в NC , но не может быть инвертирована в NC .

^{0}

$^0$

^{0}

$^0$

Юкка Суомела

Спасибо, это именно то, что я искал. Может быть, один из вас хочет сделать репост в ответ? Знаете ли вы, есть ли что-то подобное по сложности времени?

Джо Фицсимонс

Ответы:

Меня попросили перепостить мой комментарий. Я указал на эту статью Hastad, которая показывает, что в существуют перестановки , которые P-трудно инвертировать: $NC^0$

http://dx.doi.org/10.1016/0020-0190(87)90053-6 (PS)

Робин Котари
источник

Спасибо, это и продолжение Юкки было именно тем, что я искал.

Джо Фицсимонс

Для логических цепей на основе полного двоичного кода (с мерой сложности представляющей собой число затворов в минимальной схеме) наилучшее известное соотношение для перестановок $C(f)$ . Насколько я знаю, лучшая константа была получена вэтой работеХильтгеном и равна 2. $\frac{C(f^{-1})}{C(f)} = const$

Редактировать. Поскольку вы хотите, чтобы отношение росло с ростом , это не отвечает на ваш вопрос. Тем не менее, для булевых схем на полной двоичной основе ничего лучше не известно. $n$

Григорий Ярославцев
источник

Ну, тот факт, что ничего лучшего не известно, действительно является ответом.

Джо Фицсимонс

Я также предлагаю прочитать раздел 1.2 «Вычислительная асимметрия» следующей статьи: Жан-Камиль Бирже, Односторонние перестановки, Вычислительная асимметрия и искажение, Журнал алгебры, 320 (11), Вычислительная алгебра, 1 декабря 2008 г., страницы 4030-4062 , Кроме того, вас может заинтересовать эта ссылка: springerlink.com/content/4318u2t21682752u

MS Dousti

Продолжением работы Хильтгена является статья Хирша и Николенко, показывающая функцию с постоянным промежутком между ее вычислением и инвертированием, но там, где есть также люк, позволяющий облегчить инверсию: logic.pdmi.ras.ru/~hirsch/ paper / 09csr.ps.gz

user686

Смотрите также этот доклад Масси: iacr.org/publications/dl/massey96/html/massey.html

user686

Наконец, позвольте мне добавить, что было бы большим прорывом показать существование семейства функций со сверхконстантным промежутком: показ такого промежутка будет означать, что (поисковая версия) circuit-SAT не имеет цепей линейного размера ,

user686

Прежде всего, я хотел бы отметить, что сюръективность не является четко определенной без предварительного определения кодомена функции. Итак, в моем описании ниже я буду явно ссылаться на кодомен, над которым функция сюръективна.

Обе функции дискретного логарифма или RSA являются перестановками, которые, как предполагается, трудно инвертировать. Ниже я опишу функцию дискретного логарифма.

Пусть - битное простое число, а - генератор мультипликативной группы . Определите как $p_n$ $n$ $g$ $\mathbb{Z}_{p_n}^*$ $f_n \colon \mathbb{Z}_{p_n} \to \mathbb{Z}_{p_n}$ . $f_n(x) = g^x \pmod{p_n}$

$f_n$ $\mathbb{Z}_{p_n}$ $f_n$

М.С. Дусти
источник

Ну, они имеют одинаковую сложность для вычисления и инвертирования на квантовом компьютере, так что я вроде бы предположил, что не было доказательства того, что им требовались разные ресурсы, только куча неудачных попыток придумать алгоритмы полиномиального времени.

Джо Фицсимонс

Хорошо, я думаю, что вы, возможно, неправильно поняли смысл моего вопроса. Я знаю, что существует множество функций, которые трудно перевернуть, и это составляет основу криптографии с открытым ключом. То, что мне нужно, это случай, когда есть доказанное различие, даже если оно относительно умеренное (я был бы совершенно счастлив с функцией, которая использует O (n) для вычисления и O (n log n) для инвертирования, например).

Джо Фицсимонс

[Относительно 1-го комментария] Вы ищете одностороннюю семью перестановок. Простое существование таких конструкций, даже в модели вычислений машины Тьюринга, еще предстоит доказать (доказательство этого приводит к доказательству существования криптографии с открытым ключом. См. Случай 5 в cstheory.stackexchange.com/questions/). 1026 /… ) Следовательно, вы не можете полагаться на недоказанные предположения. Однако, если вам нужно допущение, которое работает как в модели машины Тьюринга, так и в квантовой модели, я могу предоставить вам подробную информацию о допущениях, основанных на твердости «проблемы решетки».

MS Dousti

Я только ищу очень слабую форму односторонней функции, и я не уверен в статусе проблемы для достаточно слабых условий. Я, конечно, не требую экспоненциальной разницы.

Джо Фицсимонс

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

Джо Фицсимонс