NP — це клас мов, які мають поліноміальні верифікатори часу
Клас NP, що означає «недетермінований поліноміальний час», є фундаментальним поняттям у теорії складності обчислень, підгалузі теоретичної інформатики. Щоб зрозуміти NP, потрібно спочатку зрозуміти поняття проблем прийняття рішень, які є питаннями з відповіддю «так чи ні». Мова в цьому контексті відноситься до набору рядків над деяким алфавітом, де кожен рядок кодує екземпляр проблеми прийняття рішення.
Кажуть, що мова (L) знаходиться в NP, якщо існує верифікатор поліноміального часу для (L). Верифікатор — це детермінований алгоритм (V), який приймає два входи: екземпляр (x) і сертифікат (y). Сертифікат (y) також відомий як «свідок» або «доказ». Верифікатор (V) перевіряє, чи підтверджує сертифікат (y) приналежність (x) до мови (L). Формально, мова (L) знаходиться в NP, якщо існує алгоритм поліноміального часу (V) і поліном (p(n)), що для кожного рядка (x в L) існує рядок (y) з ( |y|. leq p(|x|)) і (V(x, y) = 1). І навпаки, для будь-якого рядка (x, не в L) не існує такого рядка (y), що (V(x, y) = 1).
Щоб прояснити цю концепцію, розглянемо добре відому проблему «булевої виконуваності» (SAT). Проблема SAT запитує, чи існує присвоєння істинних значень змінним у даній булевій формулі, щоб формула оцінювалася як істина. Проблема SAT полягає в NP, тому що, враховуючи булеву формулу ( phi ) і присвоєння ( alpha ) значень істинності її змінним, можна перевірити за поліноміальний час, чи ( alpha ) задовольняє ( phi ). Тут екземпляр ( x ) — це булева формула ( phi ), а сертифікат ( y ) — це призначення ( alpha ). Верифікатор (V) перевіряє, чи (alpha) робить (phi) істинним, що можна зробити за поліноміальний час відносно розміру (phi).
Іншим показовим прикладом є проблема «Гамільтонів шлях». Ця задача запитує, чи існує шлях у даному графі, який відвідує кожну вершину рівно один раз. Проблема Гамільтонового шляху також є в NP, оскільки, маючи граф (G) і послідовність вершин (P), можна перевірити за поліноміальний час, чи є (P) гамільтоновим шляхом у (G). У цьому випадку екземпляром ( x ) є граф ( G ), а сертифікатом ( y ) є послідовність вершин ( P ). Верифікатор (V) перевіряє, чи (P) утворює гамільтонів шлях, що можна зробити за поліноміальний час відносно розміру (G).
Концепція верифікації поліноміального часу є важливою, оскільки вона надає спосіб охарактеризувати проблеми, які можна ефективно перевірити, навіть якщо знайти рішення може бути обчислювально неможливо. Це призводить до відомого питання про те, чи (P = NP), яке запитує, чи кожна проблема, розв’язок якої можна перевірити за поліноміальний час, також може бути розв’язана за поліноміальний час. Клас ( P ) складається з проблем прийняття рішень, які можна розв’язати за поліноміальний час за допомогою детермінованої машини Тьюринга. Якщо ( P = NP ), це означатиме, що кожна задача з верифікатором поліноміального часу також має розв’язувач поліноміального часу. Це питання залишається однією з найважливіших відкритих проблем інформатики.
Одна з ключових властивостей NP полягає в тому, що він закритий щодо скорочень за поліноміальним часом. Скорочення за поліноміальним часом від мови ( L_1 ) до мови ( L_2 ) є обчислюваною за поліноміальним часом функцією ( f ), такою, що ( x в L_1 ) тоді і тільки тоді, коли ( f(x) в L_2 ). Якщо існує скорочення за поліноміальним часом від (L_1) до (L_2) і (L_2) знаходиться в NP, тоді (L_1) також знаходиться в NP. Ця властивість є важливою у вивченні NP-повноти, яка визначає «найскладніші» проблеми в NP. Задача є NP-повною, якщо вона знаходиться в NP, і кожна задача в NP може бути зведена до неї за поліноміальний час. Проблема SAT була першою проблемою, яка доведена як NP-повна, і вона служить основою для доведення NP-повноти інших задач.
Щоб додатково проілюструвати концепцію верифікації поліноміального часу, розглянемо проблему «Сума підмножини». У цій задачі запитується, чи існує підмножина заданого набору цілих чисел, сума якої дорівнює вказаному цільовому значенню. Проблема суми підмножини є в NP, тому що, маючи набір цілих чисел (S), цільове значення (t) і підмножину (S') (S), можна за поліноміальний час перевірити, чи сума елементів у (S') дорівнює (t). Тут примірник ( x ) — це пара ( (S, t) ), а сертифікат ( y ) — підмножина ( S' ). Верифікатор (V) перевіряє, чи дорівнює сума елементів у (S') (t), що можна зробити за поліноміальний час відносно розміру (S).
Важливість верифікації поліноміального часу виходить за рамки теоретичних міркувань. На практиці це означає, що для проблем у NP, якщо надано запропоноване рішення (сертифікат), його можна ефективно перевірити. Це має значні наслідки для криптографічних протоколів, проблем оптимізації та різних сфер, де важлива перевірка правильності рішення.
Підводячи підсумок, клас NP охоплює проблеми вирішення, для яких запропоноване рішення може бути перевірено за поліноміальний час за допомогою детермінованого алгоритму. Ця концепція є основоположною в теорії обчислювальної складності та має глибоке значення як для теоретичних, так і для практичних аспектів інформатики. Вивчення NP, верифікованості поліноміального часу та пов’язаних концепцій, таких як NP-повнота, продовжує залишатися активною та критичною областю досліджень.
Інші останні запитання та відповіді щодо складність:
- Чи клас PSPACE не дорівнює класу EXPSPACE?
- Чи є клас складності P підмножиною класу PSPACE?
- Чи можемо ми довести, що класи Np і P однакові, знайшовши ефективне поліноміальне рішення для будь-якої повної проблеми NP на детермінованому TM?
- Чи може клас NP дорівнювати класу EXPTIME?
- Чи існують у PSPACE проблеми, для яких невідомий алгоритм NP?
- Чи може проблема SAT бути повною проблемою NP?
- Чи може проблема бути в класі складності NP, якщо існує недетермінована машина Тьюринга, яка розв’яже її за поліноміальний час
- Чи дійсно P і NP є однаковим класом складності?
- Чи кожна контекстно-вільна мова відноситься до класу складності P?
- Чи існує протиріччя між визначенням NP як класу задач вирішення з верифікаторами поліноміального часу та тим фактом, що задачі в класі P також мають верифікатори поліноміального часу?
Більше запитань і відповідей див. у розділі Складність