Недетермінована машина Тюрінга: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
|||
Рядок 37:
== Приклад ==
Розглянемо задачу перевірки того що дане ''b''-розрядне [[ціле число]] ''N'' (''2<sup>b-1</sup>≤N<2<sup>b</sup>'') є складовим. Тоді ''b''
Недетермінований алгоритм для цього завдання може бути
* Вибрати недетермінованої ціле число ''m'' таке що
* Розділити націло ''N'' на ''m'', залишок позначимо через ''a''.
* Якщо {{mvar|a}} = 0 видати відповідь
(Алгоритм написаний не безпосередньо у вигляді визначення машини Тьюринга.)
Під час обчислення цього алгоритму визначальною частиною є час виконання ділення, яке може бути виконано за ''[[O большое|O]](b<sup>2</sup>)'' кроків, що являє собою поліноміальний час. Таким чином завдання знаходиться в [[Клас складності NP|класі NP]].
Для реалізації такого часу обчислення, потрібно вдало вибирати число
Якщо моделювати цей алгоритм на детермінованій [[Машина Тюрінга|машині Тюрінга]], пробуючи по черзі всі можливі варіанти, потрібно перевірити ''N-2=O(2<sup>b</sup>)'' гілок. Таким чином загальний час обчислень буде ''O(b<sup>2</sup>2<sup>b</sup>)'' кроків, що є вже експоненціальне час, яке істотно більше ніж поліноміальний час. Таким чином цей алгоритм не потрапляє в [[Клас складності P|клас P]]. (Проте, можуть бути застосовані інші, більш швидкі алгоритми для цього завдання, які працюють за поліноміальний час, і таким чином завдання потрапляє в [[Клас складності P|клас P]].)
| |||