Проблема решения

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

Любую проблему принятия решения можно преобразовать в функциональную задачу вычисления характеристической функции множества, связанного с проблемой решения. Если эта функция вычислима, то соответствующая проблема принятия решения разрешима. Однако это сокращение является более либеральным, чем стандартное сокращение, используемое для вычисления сложности (иногда называемое сокращением «много-один» за полиномиальное время); например, сложность характеристических функций NP-полной задачи и ее ко-NP-полного дополнения совершенно одинакова, даже если основные проблемы решения не могут считаться эквивалентными в некоторых типичных моделях вычислений.

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

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

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

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

См. также

ВСЕ (сложность)
Вычислительная задача
Разрешимость (логика) – для задачи определения того, является ли формула следствием логической теории .
Проблема с поиском
Задача на счет (сложность)
Словесная задача (математика)

Ссылки

Козен, округ Колумбия (2012). Автоматы и вычислимость . Спрингер. ISBN 978-1-4612-1844-9 .
Хартли, Роджерс-младший (1987). Теория рекурсивных функций и эффективная вычислимость . МТИ Пресс. ISBN 978-0-262-68052-3 .
Сипсер, М. (2020). Введение в теорию вычислений . Cengage Обучение. ISBN 978-0-357-67058-3 .
Соаре, Роберт И. (1987). Рекурсивно перечислимые множества и степени . Спрингер. ISBN 0-387-15299-7 .
Кренинг, Даниэль ; Стрихман, Офер (23 мая 2008 г.). Процедуры принятия решений . Спрингер. ISBN 978-3-540-74104-6 .
Брэдли, Аарон; Манна, Зоар (3 сентября 2007 г.). Расчет вычислений . Спрингер. ISBN 978-3-540-74112-1 .

^ «CS254: Сложность вычислений: Лекция 2» (PDF) . Архивировано (PDF) из оригинала 10 октября 2015 г.

[1] «CS254: Сложность вычислений: Лекция 2» (PDF) . Архивировано (PDF) из оригинала 10 октября 2015 г.

[ 1 ]