Класи P та NP

Означення. P-задачею називається задача, яка може бути розв'язана на детермінованій машині Тюрінга за поліноміальний час O (nm), де n - розмір задачі. Іншими словами, P-задача - це задача, для розв'язку якої існує поліноміальний алгоритм.

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

Формально інструкцію не детермінованої машини Тюрінга можна записати у вигляді:

aisk→SAI,

це означає, що, якщо машина перебуває у стані sk і читає символ ai, вона породжує певну кількість нових машин, кожна з яких записує деякий символ з S, переходить до деякого стану з A і зсувається вправо, вліво, або залишається на місці. Можна вважати, що всі породжені машини продовжують перебір варіантів.

Означення. NP-задачею називається задача, яка може бути розв'язана на детермінованій машині Тюрінга за поліноміальний час O (nm), де n - розмір задачі.

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

Як визначається алгоритм?

Яким вимогам має задовольняти алгоритм?

Яка функція є обчислювальною?

Що таке часова складність алгоритму?

Що таке ємнісна складність алгоритму?

Як описується складність алгоритму?

Які ви знаєте класи алгоритмів?

Що називається P - задачею?

<== попередня сторінка	\|	наступна сторінка ==>
Приклад.	\|	NP-повні задачі.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.