TFNP - TFNP

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

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

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

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

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

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

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

F (NP ${displaystyle cap}$ coNP)

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

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

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

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

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

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

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

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

PLS

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

Данные входные цепи А и B каждый с п входные и выходные биты, найти Икс такой, что А (В (х)) ≤ А (Х).

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

PPA

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

PPP

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

Данная схема C с п входные и выходные биты, найти Икс такой, что С (х) = 0 или же х ≠ у такой, что С (х) = С (у).

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

PPAD

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

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

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

CLS

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

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

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

FP

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

Рекомендации