~~~~~~~~~~~~~~~~~~~~ Arc.Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~ 
Номер скриншота №:
✰ 0CCB64523C6CA0C418DA1A45B0B3C962__1698706920 ✰
Заголовок документа оригинал.:
✰ Decision problem - Wikipedia ✰
Заголовок документа перевод.:
✰ Проблема принятия решения — Википедия, бесплатная энциклопедия ✰
Снимок документа находящегося по адресу (URL):
✰ https://en.wikipedia.org/wiki/Decision_problem ✰
Адрес хранения снимка оригинал (URL):
✰ https://arc.ask3.ru/arc/aa/0c/62/0ccb64523c6ca0c418da1a45b0b3c962.html ✰
Адрес хранения снимка перевод (URL):
✰ https://arc.ask3.ru/arc/aa/0c/62/0ccb64523c6ca0c418da1a45b0b3c962__translat.html ✰
Дата и время сохранения документа:
✰ 08.06.2024 20:36:40 (GMT+3, MSK) ✰
Дата и время изменения документа (по данным источника):
✰ 31 October 2023, at 02:02 (UTC). ✰ 

~~~~~~~~~~~~~~~~~~~~~~ Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~~ 
Сервисы Ask3.ru: 
 Архив документов (Снимки документов, в формате HTML, PDF, PNG - подписанные ЭЦП, доказывающие существование документа в момент подписи. Перевод сохраненных документов на русский язык.)https://arc.ask3.ruОтветы на вопросы (Сервис ответов на вопросы, в основном, научной направленности)https://ask3.ru/answer2questionТоварный сопоставитель (Сервис сравнения и выбора товаров) ✰✰
✰ https://ask3.ru/product2collationПартнерыhttps://comrades.ask3.ru


Совет. Чтобы искать на странице, нажмите Ctrl+F или ⌘-F (для MacOS) и введите запрос в поле поиска.
Проблема принятия решения , бесплатная энциклопедия Jump to content

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

Из Википедии, бесплатной энциклопедии
Задача решения имеет только два возможных выхода ( да или нет ) на любом входе.

В теории вычислимости и теории сложности вычислений проблема принятия решения — это вычислительная задача, которая может быть поставлена ​​как вопрос «да-нет» относительно входных значений. Примером проблемы принятия решения является определение с помощью алгоритма того, является ли данное натуральное число простым . Другая проблема — «если даны два числа 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 .
  1. ^ «CS254: Сложность вычислений: Лекция 2» (PDF) . Архивировано (PDF) из оригинала 10 октября 2015 г.
Arc.Ask3.Ru: конец оригинального документа.
Arc.Ask3.Ru
Номер скриншота №: 0CCB64523C6CA0C418DA1A45B0B3C962__1698706920
URL1:https://en.wikipedia.org/wiki/Decision_problem
Заголовок, (Title) документа по адресу, URL1:
Decision problem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть, любые претензии не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, денежную единицу можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)