TFNP

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

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

• 1 Формальное определение
• 2 Связи с другими классами сложности
  • 2.1 F (NP $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$coNP)
  • 2.2 Подключение к NP
• 3 Известные подклассы
  • 3.1 PLS
  • 3.2 PPA
  • 3.3 PPP
  • 3.4 PPAD
  • 3.5 CLS
  • 3.6 FP
• 4 Ссылки

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

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

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

F (NP $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$coNP)

Класс сложности F (NP $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$coNP) можно определить двумя разными способами, и эти способы, как известно, не эквивалентны. Один из способов применить F к модели машины для NP $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$coNP. Известно, что в этом определении F (NP $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$coNP) совпадает с TFNP. Чтобы убедиться в этом, сначала заметьте, что включение TFNP ⊆ F (NP $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$coNP) легко следует из определений классов. Все ответы «да» на проблемы в TFNP могут быть легко проверены по определению, а поскольку проблемы в TFNP являются тотальными, ответов «нет» не существует, поэтому утверждение «нет» можно легко проверить. Для обратного включения пусть R будет бинарным отношением в F (NP $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$coNP). Разложите R на R 1$\cup \; \{\backslash \; displaystyle\; \backslash \; cup\}$R2так, чтобы (x, 0y) ∈ R 1 именно тогда, когда (x, y) ∈ R и y - ответ «да», и пусть R 2 будет (x, 1y), такое (x, y) ∈ R и y - ответ «нет». Тогда бинарное отношение R 1 ∪ R 2 находится в TFNP.

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

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

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

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

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

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

PLS

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

Для входных цепей A и B, каждая с n входными и выходными битами, найдите x такое, что A (B (x)) ≤ A (X).

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

PPA

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

PPP

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

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

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

PPAD

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

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

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

CLS

CLS (сокращение от «Continuous Local Search») - это класс задач поиска, предназначенный для моделирования процесса поиска локальных оптимумов непрерывной функции в непрерывной области. Он определяется как класс задач, которые полиномиально сводятся к проблеме непрерывной локальной точки:

Даны две липшицевы функции f и p и параметры ε и λ, найти ε-приближенную неподвижную точку f относительно p или две точки, которые нарушают λ-непрерывность p или f.

Этот класс был впервые определен Даскалакисом и Пападимитриу в 2011 году. Он находится на пересечении PPAD и PLS и был разработан как класс относительно простых проблемы оптимизации, которые все еще содержат много интересных проблем, которые считаются сложными.

FP

FP (сложность) (сокращение от «Function Polynomial») - это класс функциональных задач, которые могут быть решены за детерминированное полиномиальное время. FP $\subseteq \; \{\backslash \; displaystyle\; \backslash \; substeq\}$CLS, и предполагается, что это включение является строгим. Этот класс представляет класс функциональных задач, которые считаются вычисляемыми (без рандомизации). Если TFNP = FP, то P = NP ∩ coNP, что должно быть интуитивно понятным, учитывая тот факт, что TFNP = F (NP $\cap \; \{\backslash \; displaystyle\; \backslash \; cap\}$coNP). Однако обычно предполагается, что P ≠ NP ∩ coNP, и поэтому TFNP ≠ FP.