Знаймо![]() приховати рекламу
| Цей текст може містити помилки. Клас NPПлан:ВведенняВ теорії алгоритмів класом NP (від англ. non-deterministic polynomial) називають безліч завдань розпізнавання (англ.), рішення яких при наявності деяких додаткових відомостей (так званого сертифіката рішення) можна "швидко" (за час, не перевершує полінома від розміру даних) перевірити на машині Тьюринга. Еквівалентно клас NP можна визначити як містить завдання, які можна "швидко" вирішити на недетермінованої машині Тьюринга. 1. ВизначенняКлас складності NP визначається для безлічі мов, тобто множин слів над кінцевим алфавітом Σ . Мова L називається належить класу NP, якщо існують двомісний предикат Еквівалентна визначення можна отримати, використовуючи поняття недетермінованої машини Тьюринга (тобто такий машини Тьюринга, у програми якої можуть існувати різні рядки з однаковою лівою частиною). Якщо машина зустріла "розвилку", тобто неоднозначність у програмі, то далі можливі різні варіанти обчислення. Предикат 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. Серед них:
Серед всіх завдань класу NP можна виділити "найскладніші" - NP-повні задачі. Якщо вдасться вирішити будь-яку з них за полиномиальное час, то всі завдання класу NP також можна буде вирішити за полиномиальное час. ЛітератураЦей текст може містити помилки. Схожі роботи | скачати Схожі роботи: Клас co-NP Клас RP Клас Клас PP Клас PH Клас R Клас P Клас EXPTIME Клас PSPACE |