ТФНП

В теории сложности вычислений класс сложности TFNP — это класс задач с полными функциями, которые можно решить за недетерминированное полиномиальное время. То есть это класс функциональных задач, которые гарантированно имеют ответ, и этот ответ можно проверить за полиномиальное время, или, что то же самое, это подмножество FNP , где решение гарантированно существует. Аббревиатура TFNP означает «недетерминированный полином с полной функцией».

TFNP содержит множество естественных задач, представляющих интерес для ученых-компьютерщиков. Эти задачи включают факторизацию целых чисел , нахождение равновесия Нэша в игре и поиск локальных оптимумов. Широко распространено мнение, что TFNP содержит проблемы, которые неразрешимы с помощью вычислений, и было показано, что некоторые такие проблемы являются трудными в рамках криптографических предположений. Однако неизвестны результаты безусловной трудноразрешимости или результаты, показывающие NP-трудность задач TFNP. Считается, что у TFNP нет каких-либо полных проблем.

Формальное определение

Класс TFNP формально определяется следующим образом.

Бинарное отношение P ( x , y ) находится в TFNP тогда и только тогда, когда существует детерминированный алгоритм с полиномиальным временем, который может определить, выполняется ли P ( x , y ) при заданных как x, так и y , и для каждого x существует y, который не более чем полиномиально длиннее x, такой что P ( x , y ) выполняется.

Впервые он был определен Мегиддо и Пападимитриу в 1989 году. хотя проблемы TFNP и подклассы TFNP были определены и изучены ранее.

Примеры

Проблема принципа ячейки

• Входные данные : (полиномиально вычислимое) отображение f , которое отображает набор из n + 1 элементов в набор из n элементов.
• Вопрос : Найдите два предмета a и b такие, что f ( a ) = f ( b ).

Пусть x — отображение, а y — набор из двух элементов в его области определения. Бинарное отношение, о котором идет речь, P ( x , y ) имеет значение «образы обоих элементов y при x равны», что, поскольку отображение полиномиально вычислимо, полиномиально разрешимо. Более того, такой кортеж y должен существовать для любого отображения в силу принципа «ячейки» .

Связи с другими классами сложности

F(NP ∩ coNP)

Класс сложности ${\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})$ может быть определена двумя разными способами, и эти способы не являются эквивалентными. Один из способов применить F к модели машины для ${\mathsf {NP}}\cap {\mathsf {coNP}}$. Известно, что при таком определении ${\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})$ совпадает с ТФНП. Чтобы убедиться в этом, сначала заметим, что включение ${\mathsf {TFNP}}\subseteq {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})$ легко следует из определений классов. Все ответы «да» на задачи в TFNP можно легко проверить по определению, а поскольку проблемы в TFNP тотальны, ответов «нет» не существует, поэтому совершенно неверно, что ответы «нет» можно легко проверить. Для обратного включения пусть R — бинарное отношение в ${\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})$. Разложить R на $R_{1}\cup R_{2}$ такой, что $(x,0y)\in R_{1}$ именно тогда, когда $(x,y)\in R$ и y — ответ «да», и пусть R ₂ будет $(x,1y)$ такой $(x,y)\in R$ и y — ответ «нет». Тогда бинарное отношение $R_{1}\cup R_{2}$ находится в ТФНП.

Другое определение использует это ${\mathsf {NP}}\cap {\mathsf {coNP}}$ известно, что это класс проблем принятия решений с хорошим поведением , и к этому классу применяется F. Согласно этому определению, если ${\mathsf {NP}}\cap {\mathsf {coNP}}={\mathsf {P}}$ затем ${\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})={\mathsf {\color {Blue}FP}}$.

Подключение к НП

Интуиция лежит в основе отсутствия результатов NP-твердости для задач TFNP. На верхнем изображении показана типичная форма сокращения, показывающая, что проблема является NP-сложной. Экземпляры «да» соответствуют экземплярам «да», а экземпляры «нет» соответствуют отсутствию экземпляров. Нижнее изображение показывает, почему трудно показать, что проблемы TFNP являются NP-сложными. У проблем TFNP всегда есть решение, поэтому нет простого места для отображения экземпляров исходной проблемы.

NP — один из наиболее широко изучаемых классов сложности. Гипотеза о наличии неразрешимых проблем в NP широко принята и часто используется в качестве основного предположения о твердости. Поэтому вполне естественно задаться вопросом, как TFNP связан с NP. Нетрудно увидеть, что решение проблем в NP может предполагать решение проблем в TFNP. Однако не существует проблем TFNP, которые, как известно, были бы NP-сложными . Интуиция этого факта исходит из того факта, что проблемы в TFNP тотальны. Чтобы проблема была NP-трудной, должна существовать редукция некоторой NP-полной задачи к интересующей задаче. Типичное сведение от проблемы A к проблеме B выполняется путем создания и анализа карты, которая отправляет экземпляры «да» в экземпляры «да» B и экземпляры «нет» A в экземпляры «нет» B. A Однако проблемы TFNP являются тотальными, поэтому для этого типа сокращения не существует случаев «нет», что затрудняет применение общих методов. Помимо этой грубой интуиции, есть несколько конкретных результатов, которые предполагают, что может быть сложно или даже невозможно доказать NP-твердость для задач TFNP. Например, если какая-либо задача TFNP NP-полна, то NP = coNP, что обычно считается ложным, но все еще остается основной открытой проблемой теории сложности. Отсутствие связей с NP является основной мотивацией изучения TFNP как отдельного независимого класса.

Известные подклассы

Структуру TFNP часто изучают посредством изучения его подклассов. Эти подклассы определяются математической теоремой, согласно которой гарантируется решение проблем. Одна из привлекательных сторон изучения подклассов TFNP заключается в том, что, хотя считается, что TFNP не имеет каких-либо полных проблем, эти подклассы определяются определенной полной проблемой, что облегчает их рассмотрение.

Схема включений между подклассами TFNP. Стрелка от класса A к классу B указывает, что является подмножеством B. A Все включения считаются строгими, хотя строгость ни одного из них не доказана безоговорочно.

Пожалуйста

Основная статья: PLS (сложность)

PLS (расшифровывается как «Полиномиальный локальный поиск») — это класс задач, предназначенных для моделирования процесса поиска локального оптимума функции. В частности, это класс задач о полных функциях, которые за полиномиальное время сводятся к следующей задаче

Учитывая входные схемы S и C, каждая из которых имеет n входных и выходных битов, найдите x такой, что $C(S(x))\leq C(X)$.

Он содержит класс CLS.

ППА

Основная статья: PPA (сложность)

PPA (сокращение от «Аргумент четности полиномиального времени») — это класс задач, решение которых гарантируется леммой о установлении связи : любой неориентированный граф с вершиной нечетной степени должен иметь другую вершину нечетной степени . Он содержит подкласс PPAD .

ГЧП

Основная статья: ГЧП (сложность)

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

Дана схема C с n входными и выходными битами. Найдите x такой, что $C(x)=0$ или x ≠ y такой, что $C(x)=C(y)$.

PPP содержит классы PPAD и PWPP. Известные проблемы этого класса включают задачу решения коротких целых чисел .

ППАД

Основная статья: ППАД

PPAD (расшифровывается как «Аргумент полиномиальной четности времени, направленный») — это ограничение PPA на проблемы, решения которых гарантированы направленной версией леммы о рукопожатии . Его часто определяют как набор задач, которые за полиномиальное время можно свести к «Концу строки»:

Даны схемы S и P с n входными и выходными битами. $S(0)\neq 0$ и $P(0)=0$, найдите x такой, что $P(S(x))\neq x$ или $x\neq 0$ такой, что $S(P(x))\neq x$.

PPAD находится на пересечении PPA и PPP и содержит CLS.

Здесь схема S в определении отправляет каждую точку линии своему преемнику или себе, если точка является приемником. Аналогично P отправляет каждую точку линии ее предшественнику или себе, если точка является источником. Точки за пределами всех линий идентифицируются путем их фиксации как под P , так и под S (другими словами, любые изолированные точки удаляются с графика). Тогда условие $P(S(x))\neq x$ определяет конец линии, который либо является стоком, либо таков, что S ( x ) = S ( y ) для некоторой другой точки y ; аналогично условие $S(P(x))\neq x$ определяет начало линии (поскольку мы предполагаем, что 0 является источником, в этом случае мы требуем, чтобы решение было ненулевым).

ЦЛС

Непрерывный локальный поиск (CLS) — это класс задач поиска, предназначенных для моделирования процесса поиска локального оптимума непрерывной функции в непрерывной области. Он определяется как класс задач, которые за полиномиальное время сводятся к непрерывной проблеме локальных точек:

Для заданных двух липшицевых функций S и C и параметров ε и λ найдите ε -аппроксимированную неподвижную точку S относительно C или две точки, которые нарушают λ -непрерывность C или S .

Этот класс был впервые определен Даскалакисом и Пападимитриу в 2011 году. Он содержится на пересечении PPAD и PLS, и в 2020 году было доказано, что ${\mathsf {CLS}}={\mathsf {PPAD}}\cap {\mathsf {PLS}}$. Он был разработан как класс относительно простых задач оптимизации, который до сих пор содержит много интересных задач, которые считаются сложными.

Полными задачами для CLS являются, например, поиск точки ε- KKT , нахождение ε- банаховой неподвижной точки и проблема метаметрического сокращения.

EOPL и UEOPL

EOPL и UEOPL (что означает «конец потенциальной линии» и «уникальный конец потенциальной линии») были введены в 2020 году.

EOPL фиксирует задачи поиска, которые могут быть решены с помощью локального поиска, т.е. возможен переход от одного возможного решения к следующему за полиномиальное время. Задачу в EOPL можно интерпретировать как экспоненциально большой ориентированный ациклический граф, где каждый узел является возможным решением и имеет стоимость (также называемую потенциалом), которая увеличивается по краям. Степень входа и выхода каждого узла не превышает единицы, что означает, что узлы образуют набор экспоненциально длинных линий. Конец каждой строки — это узел с наибольшей стоимостью в этой строке.EOPL содержит все задачи, которые можно за полиномиальное время свести к задаче поиска End-of-Potential-Line:

Даны входные схемы S , P каждая с n входными и выходными битами и C с n входными и m выходными битами, $S(0)\neq 0$, $P(0)=0$, и $C(0)=0$, найдите x такой, что

• х — конец строки $P(S(x))\neq x$,
• x — начало второй строки $S(P(x))\neq x\neq 0$, или
• x нарушает возрастающую стоимость $P(S(x))=x$, $x\neq S(x)$ и $C(S(x))-C(x)\leq 0$

Здесь S отправляет каждую вершину графа своему преемнику или самому себе, если вершина является стоком. Аналогично P отправляет каждую вершину графа ее предшественнику или самой себе. фиксируясь как под P, так и под S. Точки вне графика идентифицируются , Тогда первый и второй типы решений — это соответственно верхний и нижний концы линии, а третий тип решения — нарушение условия увеличения потенциала по краям. Если это последнее условие нарушено, конечная точка может не максимизировать потенциал линии. Поэтому проблема тотальная: либо найдено решение, либо найдено краткое доказательство того, что условия не выполняются.

UEOPL определяется очень похоже, но обещано, что строка всего одна. Следовательно, обнаружение второго типа решения, приведенного выше, нарушит обещание гарантировать уникальность первого типа решения. Добавлен четвертый тип решения, чтобы обеспечить еще один способ обнаружения наличия второй линии:

• две точки x , y такие, что $x\neq y,x\neq S(x),y\neq S(y)$ и либо $C(x)=C(y)$ или $C(x)<C(y)<C(S(x))$.

Решение такого типа либо указывает на то, что x и y находятся на разных строках, либо указывает на нарушение условия строгого возрастания значений в одной строке. Преимущество включения этого условия состоит в том, что найти x и y по мере необходимости может быть проще, чем искать начало их линий или явное нарушение условия возрастающей стоимости.

UEOPL содержит, среди прочего, задачу решения P-матрицы — проблему линейной дополнительности , нахождение стока Уникальной ориентации стока в кубах, решение простой стохастической игры и проблема α-сэндвича с ветчиной. Полными задачами UEOPL являются «Уникальный конец потенциальной линии», некоторые ее варианты со стоимостью, увеличивающейся ровно на 1, или экземпляр без P- схемы, и «Дискретное сокращение с одной перестановкой».

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

EOPL — это подкласс CLS, неизвестно, равны они или нет. UEOPL тривиально содержится в EOPL.

ФП

Основная статья: FP (сложность)

FP (сложность) (расшифровывается как «Функциональный полином») — это класс функциональных задач, которые можно решить за детерминированное полиномиальное время. ${\mathsf {FP}}\subseteq {\mathsf {CLS}}$, и предполагается, что это включение строгое. Этот класс представляет собой класс функциональных задач, которые считаются решаемыми вычислительно (без рандомизации). Если TFNP = FP, то ${\mathsf {P}}={\mathsf {NP}}\cap {\mathsf {coNP}}$, что должно быть интуитивно понятно, учитывая тот факт, что ${\mathsf {TFNP}}={\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})$. Однако обычно предполагается, что ${\mathsf {P}}\neq {\mathsf {NP}}\cap {\mathsf {coNP}}$, и поэтому TFNP ≠ FP.