NP-повна задача
Матеріал з Вікіпедії — вільної енциклопедії.
У теорії алгоритмів NP-повні задачі – це клас задач, що лежать у класі NP (тобто для яких поки не знайдено швидких алгоритмів рішення, але перевірка того, чи є дане рішення правильним, проходить швидко), до яких зводяться всі задачі класу NP. Це означає, що якщо знайдуть швидкий алгоритм для рішення кожної з NP-повних задач, будь-яка задача із класу NP зможе бути вирішена швидко.
[ред.] Формальне визначення
Назвемо мовою множину слів над алфавітом Σ. Задачею тут є визначення того, чи належить дане слово мові, чи ні. Мова L1 називається зводимою (за Карпом) до мови L2, якщо існує функція , що обчислюється за поліноміальний час, що володіє наступною властивістю: f(x) належить L2 тоді й тільки тоді, коли x належить L1. Мова L2 називається NP-важкою, якщо будь-яка мова із класу NP зводиться до неї. Мову називають NP-повною, якщо вона NP-важка і при цьому сама лежить у класі NP. Таким чином, якщо буде знайдений алгоритм, що вирішує хоч одну NP-повну задачу за поліноміальний час, всі NP-задачі будуть лежати в класі P.
[ред.] Гіпотеза P ≠ NP
Рівність класів P й NP вже більше 30 років є відкритою проблемою. Наукове співтовариство схиляється до негативного вирішення цього питання – у цьому випадку за поліноміальний час вирішувати NP-повні задачі не вдасться.
[ред.] Дивись також
![]() |
Це незавершена стаття про комп'ютери. Ви можете допомогти проекту, виправивши або дописавши її. |