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

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

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

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

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

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

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

Визначення [ред.ред. код]

Проблема рішень це не випадкове питання так-або-ні про нескінченну безліч вхідних даних. Через це, традиційне визначення рішення задачі еквівалентно як: набір можливих вхідних даних разом з набором входів для яких проблема повертає так. 

Ці вхідні дані можуть бути натуральні числа, але також деякі можуть приймати значення якогось іншого роду, такі як рядки над двійковою абеткою {0,1} або над якимось іншим кінцевим набором символів. Підмножина рядків, для яких проблема повертає "так" є формальною мовою, часто вирішення проблеми визначаються таким чином, як формальні мови. 

Крім того, використання такого кодування, як Нумерація Ґьоделя, будь-який рядок можна закодувати натуральним числом, за допомогою яких проблема розв'язання може бути визначена як підмножина натуральних чисел.

Приклади [ред.ред. код]

Класичним прикладом вирішуваної задачі прийняття рішення є множина простих чисел. Можна ефективно вирішити, чи є певне натуральне число простим, за допомогою тестування кожного можливого нетривіального множника. Хоча відомі набагато більш ефективні тести на простоту, існування будь-якого ефективного методу, досить для встановлення розв'язності.

Розв'язність [ред.ред. код]

Рішення проблеми А називається розв'язною, або ефективно розв'язаною, якщо А це рекурсивна множина. Задача називається частково розв'язною, напіврозв'язною, розв'язною або доказовою, якщо А це перелічувальна множина. Проблеми, що не можна розв'язати називаються нерозв'язними.

Проблема зупинки є нерозв'язною задачею; для детальнішого огляду прикладів, дивіться список нерозв'язних проблем.

Повні проблеми[ред.ред. код]

Рішення проблем можна упорядкувати відповідно до багатозначної зводимості щодо можливого скорочення таких, як поліноміальні скорочення. Рішення проблеми Р називається повним для множини завдань прийняття рішень S, якщо Р є членом і кожна проблема в S може бути зведена до P. Повне рішення проблем використовується в теорії складності обчислень для характеристики складності обчислювальних процесів рішеннь проблем. Наприклад, задача здійсненості бульових формул для класу складності NP рішення проблем під багатозначну зводимість.

Література[ред.ред. код]

  • Kozen, D.C. (1997), Automata and Computability, Springer.
  • Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
  • Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7
  • Daniel Kroening & Ofer Strichman, Decision procedures, Springer, ISBN 978-3-540-74104-6
  • Aaron Bradley & Zohar Manna, The calculus of computation, Springer, ISBN 978-3-540-74112-1