В теории вычислимости и теории сложности вычислений задача принятия решения — это вычислительная задача , которая может быть поставлена как вопрос типа «да-нет» для входных значений. Примером задачи принятия решения является решение с помощью алгоритма , является ли заданное натуральное число простым . Другой пример — задача «Данные два числа 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 . Повторно отвечая на задачу принятия решений, можно найти минимальный вес тура.
Поскольку теория задач принятия решений очень хорошо развита, исследования в области теории сложности обычно фокусируются на задачах принятия решений. Сами задачи оптимизации по-прежнему представляют интерес для теории вычислимости, а также для таких областей, как исследование операций .