Клас NP

В теорії алгоритмів класом NP (від англ. non-deterministic polynomial) називають безліч завдань розпізнавання (англ.), рішення яких при наявності деяких додаткових відомостей (так званого сертифіката рішення) можна "швидко" (за час, не перевершує полінома від розміру даних) перевірити на машині Тьюринга.

Еквівалентно клас NP можна визначити як містить завдання, які можна "швидко" вирішити на недетермінованої машині Тьюринга.

1. Визначення

Клас складності NP визначається для безлічі мов, тобто множин слів над кінцевим алфавітом Σ . Мова L називається належить класу NP, якщо існують двомісний предикат з класу P (тобто вичіслімих за полиномиальное час) і константа c> 0 такі, що для всякого слова x умова "x належить L" рівносильно умові "знайдеться y довжини менше | X | ^c такий, що вірно "(Де | x | - довжина слова x). Слово y називається сертифікатом приналежності x мови L. Таким чином, якщо у нас є слово, яке належить мові, і ще одне слово-свідок обмеженої довжини (яке буває важко знайти), то ми швидко зможемо переконатися в тому, що x дійсно належить L.

Еквівалентна визначення можна отримати, використовуючи поняття недетермінованої машини Тьюринга (тобто такий машини Тьюринга, у програми якої можуть існувати різні рядки з однаковою лівою частиною). Якщо машина зустріла "розвилку", тобто неоднозначність у програмі, то далі можливі різні варіанти обчислення. Предикат R (x) , Який представляє дана недетерміновані машина Тьюринга, вважається рівним одиниці, якщо існує хоч один варіант обчислення, який повертає 1, і нулю, якщо всі варіанти повертають 0. Якщо довжина обчислення, що дає 1, не перевершує деякого многочлена від довжини x, то предикат називається належить класу NP. Якщо у мови існує розпізнає його предикат з класу NP, то мова називається належить класу NP. Це визначення еквівалентно наведеним вище: в якості свідка можна взяти номери потрібних гілок при розвилках в обчисленні. Так як для x належить мові довжина всього шляху обчислення не перевершує многочлена від довжини x, то і довжина свідка також буде обмежена многочленом від довжини x.

Всяку завдання про приналежність слова x мови L, що лежить в класі NP, можна вирішити за експоненціальне час перебором всіх можливих сертифікатів довжини менше | X | ^c .

2. Співвідношення з іншими класами

Клас мов, доповнення яких належать NP, називається класом co-NP, хоча і не доведено, що цей клас різниться від класу NP. Перетин класів NP і co-NP містить клас P. Зокрема, клас NP включає в себе клас P. Однак нічого не відомо про суворість цього включення.

Задача про рівність класів P і NP є однією з центральних відкритих проблем теорії алгоритмів. Якщо вони рівні, то будь-яке завдання з класу NP можна буде вирішити швидко (за полиномиальное час). Проте наукове співтовариство ^{[ хто? ]} схиляється в бік негативної відповіді на це питання.

Клас NP включається в інші, більш широкі класи, наприклад, в клас PH. Існують також відкриті питання про суворість його включення в інші класи.

3. Приклади завдань класу NP

Можна навести багато завдань, про які на сьогоднішній день невідомо, чи належать вони P, але відомо, що вони належать NP. Серед них:

• Завдання здійсненності булевих формул : дізнатися з даної булевой формулою, чи існує набір входять до неї змінних, що звертає її в 1. Сертифікат - такий набір.
• Задача про кліці : по даному графу дізнатися, чи є в ньому кліки (повні подграф) заданого розміру. Сертифікат - номери вершин, що утворюють кліку.
• Визначення наявності в графі гамильтонова циклу. Сертифікат - послідовність вершин, що утворюють гамільтонів цикл.
• Задача про комівояжера - розширений і більш наближений до реальності варіант попередньої задачі.
• Існування цілочисельного рішення у заданої системи лінійних нерівностей. Сертифікат - рішення.

Серед всіх завдань класу NP можна виділити "найскладніші" - NP-повні задачі. Якщо вдасться вирішити будь-яку з них за полиномиальное час, то всі завдання класу NP також можна буде вирішити за полиномиальное час.

Література

• Завдання пошуку. Класи P і NP. Відомості. NP-повні задачі
• "Введення в структурну теорію складності". Курс лекцій.