Введение
Класс сложности
В теории вычислительной сложности класс TFNP — это класс задач с тотальной функцией, которые могут быть решены за недетерминированное полиномиальное время. Иными словами, это класс функциональных задач, для которых гарантированно существует решение, и это решение может быть проверено за полиномиальное время, или, что эквивалентно, это подмножество FNP, где существование решения гарантировано. Аббревиатура TFNP расшифровывается как "Недетерминированный полином для тотальных функций". TFNP включает множество естественных задач, представляющих интерес для специалистов в области компьютерных наук. К этим задачам относятся факторизация целых чисел, поиск равновесия Нэша и поиск локальных оптимумов. Широко распространено предположение, что TFNP содержит вычислительно неразрешимые задачи, и для нескольких таких задач была доказана сложность при криптографических предположениях. Однако известных результатов о безусловной неразрешимости или о NP-трудности задач TFNP нет. Считается, что у TFNP нет полных задач.
In computational complexity theory, the complexity class TFNP is the class of total function problems which can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial". TFNP contains many natural problems that are of interest to computer scientists. These problems include integer factorization, finding a Nash Equilibrium of a game, and searching for local optima. TFNP is widely conjectured to contain problems that are computationally intractable, and several such problems have been shown to be hard under cryptographic assumptions. However, there are no known unconditional intractability results or results showing NP hardness of TFNP problems. TFNP is not believed to have any complete problems.
Формальное определение
Формально класс 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)
Класс сложности можно определить двумя различными способами, и пока не известно, эквивалентны ли эти способы. Один из способов применяет F к модели машины для. Известно, что при этом определении совпадает с TFNP.
ППАД
PPAD (от Polynomial time Parity Argument, Directed) — это ограничение PPA на задачи, решения которых гарантированы направленной версией леммы о рукопожатии. Часто определяется как множество задач, полиномиально сводимых к задаче «Конец линии»: даны схемы S и P с n входными и выходными битами, такие что 1=S(0) ≠ 0 и 1=P(0) = 0, найти x, удовлетворяющий условию 1=P(S(x)) ≠ x или 1=x ≠ 0, при котором 1=S(P(x)) ≠ x. PPAD находится в пересечении PPA и PPP и содержит CLS. Здесь схема S в определении отображает каждую точку линии в её преемника или в саму себя, если точка является стоком. Аналогично, P отображает каждую точку линии в её предшественника или в саму себя, если точка является источником. Точки, не лежащие ни на одной линии, идентифицируются тем, что остаются фиксированными при применении как P, так и S (иными словами, любые изолированные точки удаляются из графа). Тогда условие 1=P(S(x)) ≠ x определяет конец линии, который является либо стоком, либо точкой, для которой S(x) = S(y) для некоторой другой точки y; аналогично, условие 1=S(P(x)) ≠ x определяет начало линии (поскольку мы предполагаем, что 0 является источником, мы требуем, чтобы решение было ненулевым в этом случае).
Given circuits S and P with n input and output bits 1=S(0) \ne 0 and 1=P(0) = 0, find x such that 1=P(S(x)) \ne x or 1=x \ne 0 such that 1=S(P(x)) \ne x.
PPAD is in the intersection of PPA and PPP, and it contains CLS. Here, the circuit S in the definition sends each point of the line to its successor, or to itself if the point is a sink. Likewise P sends each point of the line to its predecessor, or to itself if the point is a source. Points outside of all lines are identified by being fixed under both P and S (in other words, any isolated points are removed from the graph). Then the condition 1=P(S(x)) \ne x defines the end of a line, which is either a sink or is such that S(x) = S(y) for some other point y; similarly the condition 1=S(P(x)) \ne x defines the beginning of a line (since we assume that 0 is a source, we require the solution be nonzero in this case).
КЛС
Непрерывный локальный поиск (CLS) — это класс задач поиска, предназначенный для моделирования процесса нахождения локального оптимума непрерывной функции на непрерывной области. Он определяется как класс задач, полиномиально сводимых к задаче о непрерывной локальной точке: даны две липшицево-непрерывные функции S и C и параметры ε и λ, найти ε-приближенную неподвижную точку S относительно C или две точки, нарушающие λ-непрерывность C или S. Этот класс был впервые определен Даскалакисом и Пападимитриу в 2011 году. Он содержится в пересечении PPAD и PLS, и в 2020 году было доказано, что CLS был разработан как класс относительно простых задач оптимизации, включающий в себя множество интересных задач, которые, как считается, являются сложными. Примеры полных задач для CLS — поиск ε-KKT точки, поиск ε-неподвижной точки Банаха и задача метаметрического сжатия.
Given two Lipschitz continuous functions S and C and parameters ε and λ, find an ε approximate fixed point of S with respect to C or two points that violate the λ continuity of C or S.
This class was first defined by Daskalakis and Papadimitriou in 2011. It is contained in the intersection of PPAD and PLS, and in 2020 it has been proven that It was designed to be a class of relatively simple optimization problems that still contains many interesting problems that are believed to be hard. Complete problems for CLS are for example finding an ε KKT point, finding an ε Banach fixed point and the Meta Metric Contraction problem.
EOPL и UEOPL
EOPL и UEOPL (аббревиатуры от "конец потенциальной линии" и "уникальный конец потенциальной линии") были введены в 2020 году. Полные задачи для UEOPL включают в себя задачу об уникальном конце потенциальной линии, некоторые её варианты с ровно единичным увеличением стоимости, а также примеры без P-цепи и задачу дискретного сжатия с одной перестановкой. EOPL охватывает задачи поиска, подобные задачам UEOPL, с тем отличием, что допускается наличие нескольких линий, и осуществляется поиск любого конца линии. На данный момент неизвестны задачи, принадлежащие EOPL, но не принадлежащие UEOPL. EOPL является подклассом CLS, и неизвестно, совпадают ли эти классы. UEOPL тривиально содержится в EOPL.
ФП
FP (сложность) (от "Функциональный полином") — это класс функциональных задач, разрешимых за полиномиальное время детерминированным алгоритмом. Предполагается, что это включение строго. Этот класс представляет собой множество функциональных задач, которые считаются вычислительно разрешимыми (без использования рандомизации). Если TFNP = FP, то 1 = P = NP ∩ coNP, что должно быть интуитивно понятно, учитывая, что 1 = TFNP = F(NP ∩ coNP). Однако, обычно предполагается, что TFNP ≠ FP.