У теорії обчислюваності і теорії складності обчислень, проблема вибору або задача про ухвалення рішень — це запитання в деякій формальній системі з відповіддю так або ні, залежно від значення деяких вхідних параметрів. Рішення проблеми зазвичай з'являються в математичних питаннях алгоритмічного розв'язання, тобто в питаннях про існування ефективного методу для визначення наявності будь-якого об'єкта або його належність множині. Деякі з важливих математичних проблем нерозв'язні.
Наприклад, питання «задані два числа x і y, чи ділиться x на y без залишку?» — буде проблемою вибору. Відповідь може бути або 'так' або 'ні', і залежить від значень x і y.
Метод розв'язання проблеми вибору описаний у формі алгоритму називається алгоритмом вибору, алгоритмом ухвалення рішень або розв'язувальною процедурою для цієї проблеми. Розв'язувальна процедура для проблеми вибору «задані два числа x і y, чи x ділиться на y без залишку?» має надати покроковий набір дій для визначення чи ділиться x на y без залишку для даних x і y. Одним з таких алгоритмів є ділення в стовпчик. Якщо залишок від ділення буде нулем, то тоді відповідь 'так', інакше 'ні'. Проблема вибору, яка може бути розв'язана за допомогою алгоритму, такого як в цьому прикладі, зветься розв'язною.
Теорія складності обчислень розрізняє розв'язні проблеми вибору за складністю їхнього розв'язання. «Складний», у цьому значені, описаний в термінах потрібних найефективнішому алгоритму розв'язання певної проблеми. Теорія обчислюваності, тим часом, розрізняє нерозв'язні проблеми вибору за степенем Тюрінга, який є мірою нерозв'язності властивою будь-якому розв'язку. Проблема вибору тісно пов'язана з функціональною проблемою, яка передбачає більш складні відповіді ніж так чи ні.
Дослідження в теорії обчислень зазвичай сфокусовані на проблемах вибору, бо від цього не втрачається загальність, тому, що кожна функціональна проблема може бути перетворена у проблему вибору.
Визначення Проблема вибору це випадкове питання так-або-ні на нескінченній множині вхідних даних. Через це, традиційне визначення проблеми вибору еквівалентно такому: множина можливих вхідних даних разом з множиною вхідних даних для яких проблема повертає так.
Ці вхідні дані можуть бути натуральними числа, але також деякі можуть набувати значень якогось іншого роду, такі як рядки над двійковою абеткою {0,1} або над якоюсь іншою скінченною множиною символів. Підмножина рядків, для яких проблема повертає «так» є формальною мовою, часто вирішення проблеми визначаються таким чином, як формальні мови.
Крім того, якщо використовувати кодування на кшталт нумерації Геделя, то будь-який рядок можна закодувати натуральним числом, що дозволяє визначити проблему розв'язання як підмножину натуральних чисел.
Приклад Класичним прикладом, який розв'язується проблемою вибору є множина простих чисел. Можна ефективно вирішити, чи є задане натуральне число простим, за допомогою перевіркою кожним можливим нетривіальним множником. Хоча відомі набагато більш ефективні тести на простоту, існування будь-якого дієвого методу достатньо для встановлення розв'язності.
Розв'язність
Рішення проблеми А називається розв'язною, або ефективно розв'язаною, якщо А — це рекурсивна множина. Задача називається частково розв'язною, напіврозв'язною, розв'язною або доказовою, якщо А — це . Проблеми, що не можна розв'язати називаються нерозв'язними.
Проблема зупинки є нерозв'язною задачею; для додаткових прикладів, дивіться .
Повні проблеми Проблеми вибору можна упорядкувати відповідно до багатозначної зводимості якщо можливе скорочення за поліноміальний час. Проблему вибору P називають повною для множини проблем вибору S, якщо Р належить S і кожна проблема в S може бути зведена до P. Повнота проблем вибору використовується в теорії складності обчислень для характеристики обчислювальної складності проблем вибору. Наприклад, задача здійсненості бульових формул є повною у класі складності NP проблем вибору при зводимості за поліноміальний час.
Примітки
Література Мальцев А. И., Алгоритмы и рекурсивные функции, Наука, 1986. Kozen, D.C. (2012), Automata and Computability, Springer. , The Theory of Recursive Functions and Effective Computability, MIT Press, (paperback), (1996), Introduction to the Theory of Computation, PWS Publishing Co. Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, & Ofer Strichman, Decision procedures, Springer, Aaron Bradley & Zohar Manna, The calculus of computation, Springer,