Проблема вибору має тільки два можливих виходи, так чи ні (або 1 чи 0) для будь-якого входу.
У теорії обчислюваності і теорії складності обчислень, проблема вибору або задача про ухвалення рішень — це запитання в деякій формальній системі з відповіддю так або ні, залежно від значення деяких вхідних параметрів. Рішення проблеми зазвичай з'являються в математичних питаннях алгоритмічного розв'язання, тобто в питаннях про існування ефективного методу для визначення наявності будь-якого об'єкта або його належність множині. Деякі з важливих математичних проблем нерозв'язні.

Наприклад, питання «задані два числа 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, 




