Введение

Проблема "да/нет" в информатике и теории сложности

В теории вычислимости и теории вычислительной сложности проблема "да/нет" (или задача принятия решения) – это вычислительная задача, которая может быть сформулирована в виде вопроса, требующего ответа "да" или "нет" на основе входных данных. Примером такой задачи является определение с помощью алгоритма, является ли заданное натуральное число простым. Другой пример – вопрос: "при заданных двух числах x и y, делится ли x на y без остатка?". Ответ будет либо "да", либо "нет" в зависимости от значений x и y. Метод решения задачи "да/нет", представленный в виде алгоритма, называется процедурой решения для этой задачи. Процедура решения для задачи "при заданных двух числах x и y, делится ли x на y без остатка?" предоставит шаги для определения, делится ли x на y без остатка. Одним из таких алгоритмов является деление с остатком. Если остаток равен нулю, ответ "да", иначе – "нет". Задача "да/нет", которую можно решить алгоритмически, называется разрешимой (или вычислимой). Задачи "да/нет" часто возникают в математических вопросах о разрешимости, то есть о существовании эффективного метода для определения существования некоторого объекта или принадлежности объекта к множеству; некоторые из наиболее важных математических задач являются неразрешимыми. Область вычислительной сложности классифицирует разрешимые задачи "да/нет" по степени их сложности. "Сложность" в данном контексте определяется с точки зрения вычислительных ресурсов, необходимых наиболее эффективному алгоритму для решения конкретной задачи. В то же время, область теории рекурсии классифицирует неразрешимые задачи "да/нет" по степени Тьюринга, которая является мерой невычислимости, присущей любому решению.

Определение

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

Примеры

Классическим примером разрешимой задачи принятия решения является множество простых чисел. Можно эффективно определить, является ли данное натуральное число простым, проверяя каждый возможный нетривиальный делитель. Хотя известны гораздо более эффективные методы проверки на простоту, само существование любого эффективного метода достаточно для установления разрешимости.

Решаемость

Проблема принятия решения является разрешимой или эффективно разрешимой, если множество входных данных (или натуральных чисел), для которых ответ положительный, является рекурсивным множеством. Проблема является частично разрешимой, полуразрешимой, разрешимой или доказуемой, если множество входных данных (или натуральных чисел), для которых ответ положительный, является рекурсивно перечислимым множеством. Проблемы, которые не разрешимы, называются неразрешимыми. Для них невозможно создать алгоритм, эффективный или иным образом, который бы их решал. Задача останова является важной неразрешимой проблемой принятия решения; для получения дополнительных примеров см. список неразрешимых проблем.

Полные задачи

Проблемы принятия решений можно упорядочить в соответствии с отношением многократного сведения и связать с практическими сведениями, такими как сведения за полиномиальное время. Проблема принятия решений P называется полной для набора проблем принятия решений S, если P принадлежит S и любая проблема из S может быть сведена к P. Полные проблемы принятия решений используются в теории вычислительной сложности для характеризации классов сложности проблем принятия решений. Например, задача булевой выполнимости является полной для класса NP проблем принятия решений при сведениях за полиномиальное время.

Проблемы с функцией

Проблемы принятия решений тесно связаны с функциональными проблемами, которые могут иметь ответы, более сложные, чем простое «да» или «нет». Соответствующая функциональная проблема: «при заданных двух числах x и y, чему равно x, деленное на y?». Функциональная проблема состоит из частной функции f; неформально, «задача» заключается в вычислении значений f для тех входных данных, для которых она определена. Любую функциональную проблему можно свести к проблеме принятия решений; проблема принятия решений — это просто график соответствующей функции. (График функции f — это множество пар (x, y) таких, что f(x) = y.) Если бы эта проблема принятия решений была эффективно разрешима, то и функциональная проблема была бы разрешима. Однако данное сведение не учитывает вычислительную сложность. Например, возможно, что график функции может быть определим за полиномиальное время (в этом случае время работы вычисляется как функция от пары (x, y)), в то время как сама функция не вычислима за полиномиальное время (в этом случае время работы вычисляется как функция только от x). Функция f(x) = 2x обладает этим свойством. Любую проблему принятия решений можно преобразовать в функциональную проблему вычисления характеристической функции множества, связанного с этой проблемой принятия решений. Если эта функция вычислима, то связанная с ней проблема принятия решений разрешима. Однако это сведение более свободно, чем стандартное сведение, используемое в теории вычислительной сложности (иногда называемое сведением «многие к одному» за полиномиальное время); например, сложность характеристических функций NP-полной задачи и ее co-NP-полного дополнения одинакова, хотя лежащие в основе проблемы принятия решений могут не считаться эквивалентными в некоторых типичных моделях вычислений.

Проблемы оптимизации

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