В теории вычислимости и теории сложности вычислений проблема принятия решения — это вычислительная задача, которая может быть поставлена как вопрос «да-нет» относительно входных значений. Примером проблемы принятия решения является определение с помощью алгоритма того, является ли данное натуральное число простым . Другая проблема — «если даны два числа x и y , делит ли x y нацело ?». Ответ — «да» или «нет» в зависимости от значений x и y . Метод решения проблемы принятия решения, заданный в виде алгоритма , называется процедурой решения этой проблемы. Процедура решения задачи «Для данных двух чисел x и y делит ли x y поровну ?» дало бы шаги для определения того, делит ли x равномерно y . Одним из таких алгоритмов является деление в длину . Если остаток равен нулю, ответ «да», в противном случае — «нет». Задача, которую можно решить с помощью алгоритма, называется разрешимой .
Проблемы принятия решения обычно возникают в математических вопросах разрешимости , то есть в вопросе о существовании эффективного метода определения существования некоторого объекта или его членства в множестве; некоторые из наиболее важных проблем математики неразрешимы .
Область вычислительной сложности классифицирует разрешимые проблемы принятия решений в зависимости от того, насколько сложно их решить. «Сложный» в этом смысле описывается с точки зрения вычислительных ресурсов , необходимых для наиболее эффективного алгоритма для решения определенной проблемы. Тем временем в области теории рекурсии неразрешимые проблемы решения классифицируются по степени Тьюринга , которая является мерой невычислимости, присущей любому решению.
Проблема принятия решения — это вопрос «да» или «нет» для бесконечного набора входных данных. Традиционно проблему принятия решения определяют как набор возможных входных данных вместе с набором входных данных, для которых ответ « да» . [1]
Эти входные данные могут быть натуральными числами, но также могут быть значениями другого типа, например двоичными строками или строками в каком-либо другом алфавите . Подмножество строк, для которых задача возвращает «да», является формальным языком , и часто проблемы решения определяются как формальные языки.
Используя такую кодировку, как нумерация Гёделя , любую строку можно закодировать как натуральное число, с помощью чего проблему принятия решения можно определить как подмножество натуральных чисел. Следовательно, алгоритм решения проблемы заключается в вычислении характеристической функции подмножества натуральных чисел.
Классическим примером разрешимой проблемы решения является набор простых чисел. Можно эффективно решить, является ли данное натуральное число простым, проверив все возможные нетривиальные факторы. Хотя известны гораздо более эффективные методы проверки простоты , существования любого эффективного метода достаточно, чтобы установить разрешимость.
Проблема принятия решения является разрешимой или эффективно решаемой, если набор входных данных (или натуральных чисел), для которых ответ положительный, является рекурсивным набором . Проблема является частично разрешимой , полуразрешимой , разрешимой или доказуемой, если набор входных данных (или натуральных чисел), для которых ответ положительный, является рекурсивно перечислимым набором . Проблемы, которые неразрешимы, являются неразрешимыми . Для них невозможно создать алгоритм, эффективный или нет, который бы их решал.
Проблема остановки является важной неразрешимой проблемой принятия решения; дополнительные примеры см. в списке неразрешимых проблем .
Задачи принятия решений можно упорядочить в соответствии со сводимостью «многие к одному» и соотнести с возможными сокращениями, такими как сокращения за полиномиальное время . Задача решения P называется полной для множества проблем решения S , если P является членом S и каждая проблема в S может быть сведена к P . Задачи полного решения используются в теории сложности вычислений для характеристики классов сложности задач принятия решений. Например, булева проблема выполнимости является полной для класса NP задач решения при полиномиальной сводимости.
Проблемы принятия решений тесно связаны с функциональными проблемами , ответы на которые могут быть более сложными, чем простое «да» или «нет». Соответствующая функциональная задача: «Дано два числа x и y , чему равно x, разделенное на y ?».
Функциональная задача состоит из частичной функции f ; неформальная «проблема» состоит в том, чтобы вычислить значения f на входных данных, для которых она определена.
Любую функциональную проблему можно превратить в проблему решения; проблема решения — это просто график связанной функции. (График функции f — это набор пар ( x , y ) таких, что f ( x ) = y .) Если бы эта проблема принятия решения была эффективно разрешима, то и проблема с функцией была бы также разрешима. Однако это сокращение не учитывает вычислительную сложность. Например, график функции может быть разрешим за полиномиальное время (в этом случае время выполнения вычисляется как функция пары ( x , y )), когда функция не вычислима за полиномиальное время (в этом случае время выполнения случая рассчитывается как функция только от x ). Этим свойством обладает функция f ( x ) = 2 x .
Любую проблему принятия решения можно преобразовать в функциональную задачу вычисления характеристической функции множества, связанного с проблемой решения. Если эта функция вычислима, то соответствующая проблема принятия решения разрешима. Однако это сокращение является более либеральным, чем стандартное сокращение, используемое для вычислительной сложности (иногда называемое сокращением «много-один» за полиномиальное время); например, сложность характеристических функций NP-полной задачи и ее ко-NP-полного дополнения совершенно одинакова, даже если основные проблемы решения не могут считаться эквивалентными в некоторых типичных моделях вычислений.
В отличие от задач принятия решений, для которых существует только один правильный ответ для каждого входного сигнала, задачи оптимизации связаны с поиском лучшего ответа на конкретный входной сигнал. Проблемы оптимизации естественным образом возникают во многих приложениях, таких как задача коммивояжера и многие вопросы линейного программирования .
Проблемы функций и оптимизации часто преобразуются в проблемы принятия решений, рассматривая вопрос о том, равен ли результат заданному значению , меньше или равен ему . Это позволяет изучить сложность соответствующей проблемы решения; и во многих случаях исходную функцию или задачу оптимизации можно решить путем решения соответствующей проблемы решения. Например, в задаче о коммивояжере задача оптимизации состоит в том, чтобы составить тур с минимальным весом. Соответствующая проблема принятия решения такова: для каждого N определить , есть ли в графе какой-либо обход с весом меньше N. Многократно отвечая на задачу решения, можно найти минимальный вес тура.
Поскольку теория проблем принятия решений очень хорошо развита, исследования в области теории сложности обычно фокусируются на проблемах принятия решений. Сами задачи оптимизации по-прежнему представляют интерес в теории вычислимости, а также в таких областях, как исследование операций .