Проблема вибору

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Проблема вибору має тільки два можливих виходи, так чи ні (або 1 чи 0) для будь-якого входу.

У теорії обчислень і теорії складності обчислень, проблема вибору або задача про приймання рішень це запитання в деякій формальній системі з відповіддю так або ні, залежно від значення деяких вхідних параметрів. Наприклад, «дані два числа x і y, чи ділиться x на y без залишку?» — проблема вибору. Відповідь може бути або 'так' або 'ні', і залежить від значень x і y.

Метод розв'язання проблеми вибору даний у формі алгоритму називається алгоритмом вибору, алгоритмом приймання рішень або розв’язувальною процедурою для цієї проблеми. Розв'язувальна процедура для проблеми вибору «дані два числа x і y, чи x ділиться на y без залишку?" має надати покроковий набір дій для визначення чи ділиться x на y без залишку для даних x і y. Одним з таких алгоритмів є ділення в стовпчик. Якщо залишок нуль, тоді відповідь 'так' інакше 'ні'. Проблема вибору, яка може бути розв'язана за допомогою алгоритму, такого як в цьому прикладі, зветься розв'язною.

Теорія складності обчислень розрізняє розв'язні проблеми вибору за складністю їхнього розв'язання. «Складний», у цьому значені, описаний в термінах обчислювальних ресурсів потрібних найефективнішому алгоритму для певної проблеми. Теорія обчислень, тим часом, розрізняє нерозв'язні проблеми вибору за степенем Тюрінга, який є мірою неров'язності властивої будь-якому розв'язку.

Дослідження в теорії обчислень зазвичай сфокусовані на проблемах вибору, від цього не втрачається загальність, бо кожна функціональна проблема може бути перетворена у проблему вибору.