В теории сложности вычислений , то класс сложности TFNP является классом общих проблем функции , которые могут быть решены в недетерминированном полиномиальное время. То есть это класс функциональных задач, на которые гарантированно будет ответ, и этот ответ можно проверить за полиномиальное время, или, что эквивалентно, это подмножество FNP, где гарантированно существует решение. Аббревиатура TFNP означает «Недетерминированный многочлен общей функции».
TFNP содержит множество естественных проблем, которые интересуют компьютерных ученых. Эти проблемы включают целочисленную факторизацию , поиск равновесия по Нэшу в игре и поиск локальных оптимумов. Широко распространено предположение, что TFNP содержит проблемы, которые сложно решить с помощью вычислений, и было показано, что несколько таких проблем трудноразрешимы при криптографических предположениях. [1] [2] Однако нет никаких известных результатов безусловной неразрешимости или результатов, показывающих NP-трудность проблем TFNP. Считается, что у TFNP нет каких-либо полных проблем. [3]
Формальное определение
Класс TFNP формально определяется следующим образом.
- Бинарное отношение P ( x , y ) находится в TFNP тогда и только тогда, когда существует детерминированный алгоритм полиномиального времени, который может определить , выполняется ли P ( x , y ) для обоих x и y , и для каждого x существует y, который не более чем полиномиально длиннее x такой, что выполняется P ( x , y ).
Впервые он был определен Мегиддо и Пападимитриу в 1989 г. [4], хотя задачи TFNP и подклассы TFNP были определены и изучены ранее. [5]
Связи с другими классами сложности
F (NP coNP)
Класс сложности F (NP coNP) можно определить двумя разными способами, и эти способы не известны как эквивалентные. Один из способов применяет F к модели машины для NPcoNP. Известно, что при таком определении F (NPcoNP) совпадает с TFNP. [4] Чтобы убедиться в этом, сначала заметим, что включение TFNP ⊆ F (NPcoNP) легко следует из определений классов. Все ответы «да» на проблемы в TFNP могут быть легко проверены по определению, а поскольку проблемы в TFNP являются общими, ответов «нет» не бывает, поэтому утверждение «нет» можно легко проверить. Для обратного включения пусть R - бинарное отношение в F (NPcoNP). Разложить R на R 1 R 2 такое, что (x, 0y) ∈ R 1 именно тогда, когда (x, y) ∈ R и y - ответ «да», и пусть R 2 будет (x, 1y) таким (x, y) ∈ R и y это ответ «нет». Тогда бинарное отношение R 1 ∪ R 2 находится в TFNP.
В другом определении используется NP CONP , как известно, хорошо себя класс по проблемам принятия решений , и применяет F к этому классу. При таком определении, если NP coNP = P, тогда F (NP coNP) = FP .
Подключение к НП
NP - один из наиболее широко изучаемых классов сложности. Гипотеза о том, что в NP существуют неразрешимые проблемы, широко распространена и часто используется в качестве основного предположения о твердости. Поэтому естественно спросить, какое отношение TFNP имеет к NP. Нетрудно увидеть, что решения проблем в NP могут подразумевать решения проблем в TFNP. Тем не менее, проблем с TFNP, которые, как известно, являются NP-трудными, нет . Интуиция к этому факту исходит из того факта, что проблем в TFNP много. Чтобы проблема была NP-трудной, должна существовать редукция от некоторой NP-полной проблемы к интересующей проблеме. Типичное сокращение по сравнению с проблемным А к задаче B выполняется путем создания и анализа карты , которая посылает «да» экземпляры А «Да» экземпляры B и «нет» случаев А «Нет» экземпляров B . Тем не менее, проблемы с TFNP являются общими, поэтому нет «никаких» случаев для этого типа редукции, что затрудняет применение общих методов. Помимо этой грубой интуиции, есть несколько конкретных результатов, которые предполагают, что может быть трудно или даже невозможно доказать NP-твердость для проблем TFNP. Например, если какая-либо проблема TFNP является NP-полной, то NP = coNP, [3], что обычно считается ложным, но по-прежнему остается большой открытой проблемой в теории сложности. Отсутствие связи с NP является основной причиной изучения TFNP как отдельного независимого класса.
Известные подклассы
Структура TFNP часто изучается путем изучения его подклассов. Эти подклассы определяются математической теоремой, по которой гарантируются решения проблем. Одним из преимуществ изучения подклассов TFNP является то, что хотя считается, что TFNP не имеет каких-либо полных проблем, эти подклассы определяются определенной полной проблемой, что упрощает их рассуждение.
PLS
PLS (расшифровывается как «полиномиальный локальный поиск») - это класс задач, предназначенных для моделирования процесса поиска локального оптимума для функции. В частности, это класс задач полной функции, которые полиномиально сводятся к следующей задаче
- Для входных цепей S и C, каждая из которых имеет n входных и выходных битов, найдите x такое, что C (S (x)) ≤ C (X) .
Он содержит класс CLS.
PPA
PPA (расшифровывается как «аргумент полиномиального времени четности») - это класс задач, решение которых гарантируется леммой о подтверждении связи : любой неориентированный граф с вершиной нечетной степени должен иметь другую вершину нечетной степени . Он содержит подклассы PWPP и PPAD .
PPP
PPP (сокращение от «Принцип полиномиального времени») - это класс задач, решение которых гарантируется принципом «голубятни» . Точнее, это класс задач, который можно за полиномиальное время свести к задаче Голубя, определяемой следующим образом
- Для схемы C с n входными и выходными битами найдите x такое, что C (x) = 0, или x ≠ y, такое что C (x) = C (y) .
PPP содержит классы PPAD и PWPP. Известные проблемы в этом классе включают задачу решения коротких целых чисел . [6]
PPAD
PPAD ( сокращение от «Polynomial time Parity Argument, Directed») - это ограничение 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») - это класс задач поиска, предназначенный для моделирования процесса поиска локальных оптимумов непрерывной функции в непрерывной области. Он определяется как класс задач, которые за полиномиальное время сводятся к проблеме непрерывной локальной точки:
- Учитывая две непрерывные функции Липшица S и C и параметры epsi ; и λ , найти ε -approximate неподвижную точку S по отношению к С или двум точкам, нарушающим А -непрерывность C или S .
Этот класс был впервые определен Даскалакисом и Пападимитриу в 2011 году. [7] Он содержится на пересечении PPAD и PLS, а в 2020 году было доказано, что CLS = PPAD ∩ PLS. [8] Он был разработан как класс относительно простых задач оптимизации, которые по-прежнему содержат много интересных проблем, которые считаются сложными.
Полные задачи для CLS - это, например, поиск точки ε- KKT [9], нахождение фиксированной точки ε- Банаха [10] и проблема мета-метрического сжатия. [11]
EOPL и UEOPL
EOPL и UEOPL (что означает «конец потенциальной линии» и «уникальный конец потенциальной линии») были введены в 2020 г. [9]
UEOPL фиксирует задачи поиска, которые могут быть решены локальным поиском, т.е. можно перейти от одного варианта решения к следующему за полиномиальное время. Более того, проблемы в UEOPL обещают найти уникальное решение. Проблема в UEOPL может быть интерпретирована как экспоненциально большой направленный ациклический граф, где каждый узел является кандидатом на решение и имеет стоимость (также называемую потенциальной). Степень входа и выхода каждого узла не превышает одного, что означает, что узлы образуют экспоненциально длинную линию. Уникальное решение, узел с самой высокой стоимостью, находится в конце этой уникальной строки. UEOPL содержит все задачи, которые могут быть сведены за полиномиальное время к задаче поиска Unique-End-of-Potential-Line:
- Для входных цепей S , P и C, каждая из которых имеет n входных и выходных битов, S (0) ≠ 0 и P (0) = 0 , найдите x такое, что
- x - конец прямой P (S (x)) ≠ x ,
- x - начало второй строки S (P (x)) ≠ x ≠ 0 ,
- x нарушает возрастающую стоимость P (S (x)) = x , x ≠ S (x) и C (S (x)) - C (x) ≤ 0 или
- две точки x , y такие, что x ≠ y, x ≠ S (x), y ≠ S (y) и либо C (x) = C (y), либо C (x)
.
- Первый тип решения - это фактический конец строки, тогда как остальные три решения являются нарушениями свойств, которые гарантируют, что существует уникальное решение. Если какое-либо из этих свойств нарушается, единственного решения не существует. Следовательно, проблема является полной: либо найдено единственное решение, либо краткое доказательство того, что единственного решения не существует.
UEOPL содержит, среди прочего, проблемы решения P-матрицы - линейная задача дополнительности , [9] , находя мойку в ориентации раковины Уникальной в кубиках, [9] решить простую стохастическую игру [9] и сэндвич α-Ham проблема. [12] Полные задачи UEOPL - это уникальный конец потенциальной линии, некоторые его варианты с увеличением стоимости ровно на 1 или экземпляр без P- схемы, а также дискретное сжатие с одной перестановкой. [9]
EOPL улавливает проблемы поиска, подобные тем, что есть в UEOPL, с тем условием, что разрешено несколько строк и поиск выполняется с любого конца строки. В настоящее время не известно о проблемах, которые есть в EOPL, но отсутствуют в UEOPL.
EOPL - это подкласс CLS, равны они или нет - неизвестно. UEOPL тривиально содержится в EOPL.
FP
FP (сложность) (сокращение от «Function Polynomial») - это класс функциональных задач, которые могут быть решены за детерминированное полиномиальное время. FPCLS, и предполагается, что это включение строгое. Этот класс представляет класс функциональных задач, которые считаются вычислительно решаемыми (без рандомизации). Если TFNP = FP, то P = NP ∩ coNP, что должно быть интуитивно понятным, учитывая тот факт, что TFNP = F (NPcoNP). Однако обычно предполагается, что P ≠ NP ∩ coNP, и поэтому TFNP ≠ FP.
Рекомендации
- ^ Garg, Панди и Srinivasan. Возвращаясь к криптографической стойкости нахождения равновесия по Нэшу . КРИПТО 2016.
- ^ Habàcek и Йогев. Сложность непрерывного локального поиска: сложность запроса и нижние границы криптографии . SODA 2016.
- ^ а б Гольдберг и Пападимитриу. К единой теории сложности полных функций . 2018.
- ^ а б Мегиддо и Пападимитриу. Заметка о полных функциях, теоремах существования и вычислительной сложности . Теоретическая информатика 1989.
- ↑ Джонсон, Пападимитриу и Яннакакис. Насколько прост локальный поиск? . Журнал компьютерных систем, 1988.
- ^ Sotiraki, Zampetakis и Zidelis. Полнота PPP с подключениями к криптографии . FOCS 2018
- ^ Daskalakis и Papadimitriou. Непрерывный локальный поиск . SODA 2011.
- ^ Фернли, Джон; Голдберг, Пол В .; Холлендер, Александрос; Савани, Рахул (11 ноября 2020 г.). «Сложность градиентного спуска: CLS = PPAD ∩ PLS». arXiv : 2011.01929 [ cs.CC ].
- ^ а б в г д е Фернли, Джон; Гордон, Спенсер; Мехта, Рута; Савани, Рахул (декабрь 2020 г.). «Единственный конец потенциальной линии» . Журнал компьютерных и системных наук . 114 : 1–35. DOI : 10.1016 / j.jcss.2020.05.007 .
- ^ Даскалакис, Константинос; Цамос, Христос; Зампетакис, Манолис (13 февраля 2018 г.). «Обращение к теореме Банаха о неподвижной точке и ее CLS-полнота». arXiv : 1702.07339 [ cs.CC ].
- ^ Фернли, Джон; Гордон, Спенсер; Мехта, Рута; Савани, Рахул (7 апреля 2017 г.). «CLS: новые проблемы и полнота». arXiv : 1702.06017 [ cs.CC ].
- ^ Чиу, Ман-Квун; Чоудхари, Аруни; Мульцер, Вольфганг (20 марта 2020 г.). "Вычислительная сложность проблемы α-Хэма-Сэндвича". arXiv : 2003.09266 [ cs.CG ].