Введение

В математике теории вычислительной сложности, теории вычислимости и теории принятия решений, поисковая задача – это тип вычислительной проблемы, представленный бинарным отношением. Интуитивно, задача состоит в поиске структуры "y" в объекте "x". Алгоритм считается решающим задачу, если существует хотя бы одна соответствующая структура, и тогда одно вхождение этой структуры выдается в качестве результата; в противном случае алгоритм останавливается с соответствующим результатом ("не найдено" или аналогичным сообщением). Каждая поисковая задача также имеет соответствующую задачу решения, а именно:

Это определение может быть обобщено на n-арные отношения, используя любое подходящее кодирование, позволяющее сжать несколько строк в одну (например, путем последовательного перечисления с разделителем). Более формально, отношение R можно рассматривать как поисковую задачу, а машина Тьюринга, вычисляющая R, также считается решающей её. Более формально, если R – бинарное отношение, такое что область определения(R) ⊆ Γ+ и T – машина Тьюринга, то T вычисляет R, если:

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

(Обратите внимание, что граф частичной функции является бинарным отношением, и если T вычисляет частичную функцию, то существует не более одного возможного результата.) Такие задачи очень часто встречаются в теории графов и комбинаторной оптимизации, например, при поиске структур, таких как конкретные паросочетания, опциональные клики, конкретные стабильные множества и т.д., которые представляют интерес.

Цель

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