Клас складності co-NP

В теорії складності обчислень, co-NP — клас складності. Задача належить класу co-NP тоді і тільки тоді, коли компланарна до неї задача належить класу NP. Неформально, co-NP — клас задач, для яких існують ефективні (поліноміальної складності) перевірювачі для відповіді «Ні».

Візьмемо приклад NP-повної задачі про суму підмножин: «Дана скінченна множина цілих чисел. Чи є у неї хоч одна непорожня підмножина, сума елементів якої рівна нулю?» Комланарною до цієї задачі буде така: «Дана скінченна множина цілих чисел. Чи кожна непорожня має ненульову суму елементів?» Щоб довести відповідь «Ні», маємо надати якусь непорожню підмножину, сума елементів якої рівна нулю. Таке доведення легко перевірити за поліноміальний час. P, клас задач, розв'язних за поліноміальний час, є підмножиною як NP, так і co-NP. NP і co-NP вважаються (хоч це не доведено) нерівними. Якщо для якої-небудь NP-повної задачі довести, що вона належить класу co-NP, то це означало б рівність цих класів. Оскільки будь-яка NP-задача (за означенням) зводиться до NP-повної за поліноміальний час. Задача, що належить як до NP, так і до co-NP, досить ймовірно(за припущенням про нерівність цих класів) не є NP-повною.

Прикладом задачі, що належить як до NP, так і до co-NP, є факторизація числа: "дано натуральні числа m та n. Визначити, чи m має простий дільник, менший за n. Належність до NP очевидна: якщо m має такий дільник, то він і є підтвердженням відповіді. Доведення належності до co-NP складніше: для перевірки відповіді маємо перелічити прості дільники m та довести для кожного, що він є простим. Інша задача з перетину NP ∩ co-NP — перевірка чи є число простим.

Література

• Hopcroft, John E. (2000). Introduction to Automata Theory, Languages, and Computation (вид. 2nd). Boston: Addison-Wesley. ISBN 0-201-44124-1.
• Ravi B. Boppana, Johan Hastad Stathis Efstathios Zachos (1987) Does co-NP have short interactive proofs? May 1987. Information Processing Letters 25(2):127-132 DOI:10.1016/0020-0190(87)90232-8
• Lorenzo De Stefani. Fall, 2020 CS1010: Theory of Computation. Lecture 17: On NP vs CoNP, More examples of NP-Hard problems brown.edu
• Chandra Chekuri, Fall 2010 CS 473: Algorithms University of Illinois, Urbana-Champaign

Посилання

• Whats the difference between NP and co-NP 2014y.
• Types of Complexity Classes | P, NP, CoNP, NP hard and NP complete