ППП (сложность)

В теории вычислительной сложности класс сложности PPP ( полиномиальный принцип Pigeonhole ) является подклассом TFNP . Это класс задач поиска, который может быть показан как тотальный с помощью применения принципа Pigeonhole . Христос Пападимитриу представил его в той же статье, что и PPAD и PPA. ^[1] PPP содержит как PPAD , так и PWPP (полиномиальный слабый принцип Pigeonhole) в качестве подклассов. Эти классы сложности представляют особый интерес в криптографии, поскольку они тесно связаны с криптографическими примитивами, такими как односторонние перестановки и хэш-функции, устойчивые к коллизиям .

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

Для данной булевой схемы, имеющей одинаковое количество входных и выходных битов, найдите либо вход , который отображается на выход , либо два различных входа , которые отображаются на один и тот же выход .${\displaystyle С}$${\displaystyle n}$${\displaystyle x}$${\displaystyle C(x)=0^{n}}$${\displaystyle x\neq y}$${\displaystyle С(х)=С(у)}$

Задача является PPP- полной , если PIGEON также сводится к ней за полиномиальное время. Обратите внимание, что принцип Pigeonhole гарантирует, что PIGEON является тотальным. Мы также можем определить WEAK-PIGEON , для которого слабый принцип Pigeonhole гарантирует тотальность. PWPP — это соответствующий класс задач, которые сводятся к ней за полиномиальное время. ^[2] WEAK-PIGEON — это следующая задача:

Для данной булевой схемы, имеющей входные и выходные биты, найдите такую, что .${\displaystyle С}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle x\neq y}$${\displaystyle С(х)=С(у)}$

Здесь диапазон схемы строго меньше ее домена, поэтому схема гарантированно неинъективна . WEAK -PIGEON сводится к PIGEON путем добавления одного бита 1 к выходу схемы, поэтому PWPP PPP.${\displaystyle \subseteq}$

Мы можем рассматривать схему в PIGEON как вычислимую за полиномиальное время хэш-функцию. Следовательно, PPP — это класс сложности, который охватывает сложность инвертирования или поиска коллизии в хэш-функциях. В более общем смысле, отношение подклассов FNP к классам сложности за полиномиальное время может использоваться для определения существования определенных криптографических примитивов, и наоборот.

Например, известно, что если FNP = FP , то односторонние функции не существуют. Аналогично, если PPP = FP, то односторонние перестановки не существуют. ^[3] Следовательно, PPP (который является подклассом FNP) более точно охватывает вопрос существования односторонних перестановок. Мы можем доказать это, сведя задачу инвертирования перестановки на выходе к PIGEON . Постройте схему , которая вычисляет . Поскольку является перестановкой, решение PIGEON должно выводить такое , что , что подразумевает .${\displaystyle \пи}$${\displaystyle у}$${\displaystyle С}$${\displaystyle C(x)=\пи (x)\oplus y}$${\displaystyle \пи}$${\displaystyle x}$${\displaystyle C(x)=0=\пи (x)\oplus y}$${\displaystyle \пи (x)=y}$

PPP содержит PPAD как подкласс (строгое включение является открытой проблемой). Это происходит потому, что End-of-the-Line , который определяет PPAD, допускает прямое полиномиальное сведение к PIGEON . В End-of-the-Line вход является начальной вершиной в ориентированном графе , где каждая вершина имеет не более одного преемника и не более одного предшественника, представленных вычислимой за полиномиальное время функцией преемника . Определите схему , входом которой является вершина , а выходом — ее преемник, если он есть, или если его нет. Если мы представим исходную вершину как bitstring , эта схема является прямым сведением End-of-the-Line к Pigeon , поскольку любое столкновение в обеспечивает сток в .${\displaystyle с}$${\displaystyle G}$${\displaystyle f}$${\displaystyle С}$${\displaystyle x}$${\displaystyle x}$${\displaystyle с}$${\displaystyle 0^{н}}$${\displaystyle С}$${\displaystyle G}$

Задача о равных суммах — это следующая задача. Даны положительные целые числа, сумма которых меньше , найдите два различных подмножества целых чисел, которые имеют одинаковую сумму. Эта задача содержится в PPP, но неизвестно, является ли она PPP-полной.${\displaystyle n}$${\displaystyle 2^{n}-1}$

Проблема с ограничениями SIS (решение с короткими целыми числами), которая является обобщением проблемы SIS из криптографии на основе решеток, как было показано, является полной для PPP. ^[4] До этой работы единственными известными полными задачами для PPP были варианты PIGEON .

Существуют рандомизированные редукции полиномиального времени от задачи факторизации целых чисел до WEAK-PIGEON . ^[5] Кроме того, в рамках обобщенной гипотезы Римана также существуют детерминированные полиномиальные редукции. Однако все еще остается открытой проблема безусловного доказательства того, что факторизация целых чисел находится в PPP.