Клас складності co-NP: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Немає опису редагування |
Script: додавання шаблонів впорядкування |
||
(Не показана 21 проміжна версія 13 користувачів) | |||
Рядок 1: | Рядок 1: | ||
{{Без розділів|дата=червень 2023}} |
|||
В теорії складності обчислень, [[co-NP]] |
В теорії складності обчислень, [[co-NP]] — клас складності. Задача належить класу co-NP тоді і тільки тоді, коли компланарна до неї задача належить [[Клас складності NP|класу NP]]. Неформально, co-NP — клас задач, для яких існують ефективні (поліноміальної складності) перевірювачі для відповіді «Ні». |
||
Візьмемо приклад NP-повної задачі про суму підмножин: «Дана скінченна множина цілих чисел. Чи є у неї хоч одна непорожня підмножина, сума елементів якої рівна нулю?» Комланарною до цієї задачі буде така: «Дана скінченна множина цілих чисел. Чи кожна непорожня має ненульову суму елементів?» Щоб довести відповідь «Ні», маємо надати якусь непорожню підмножину, сума елементів якої рівна нулю. Таке доведення легко перевірити за поліноміальний час. |
Візьмемо приклад NP-повної [[Задача про суму підмножини|задачі про суму підмножин]]: «Дана скінченна множина цілих чисел. Чи є у неї хоч одна непорожня підмножина, сума елементів якої рівна нулю?» Комланарною до цієї задачі буде така: «Дана скінченна множина цілих чисел. Чи кожна непорожня має ненульову суму елементів?» Щоб довести відповідь «Ні», маємо надати якусь непорожню підмножину, сума елементів якої рівна нулю. Таке доведення легко перевірити за поліноміальний час. P, клас задач, розв'язних за поліноміальний час, є підмножиною як NP, так і co-NP. |
||
⚫ | |||
P, клас задач, розв’язних за поліноміальний час ,є підмножиною як NP так і co-NP. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
Прикладом задачі, що належить як до NP |
Прикладом задачі, що належить як до NP, так і до co-NP, є факторизація числа: "дано [[натуральні числа]] m та n. Визначити, чи m має [[просте число|простий]] [[дільник]], менший за n. Належність до NP очевидна: якщо m має такий дільник, то він і є підтвердженням відповіді. Доведення належності до co-NP складніше: для перевірки відповіді маємо перелічити прості дільники m та довести для кожного, що він є простим. Інша задача з перетину NP ∩ co-NP — перевірка чи є число [[просте число|простим]]. |
||
== Література == |
|||
{{rq|sources|wikify}} |
|||
* {{cite book | first = John E. | last = Hopcroft | title = Introduction to Automata Theory, Languages, and Computation | publisher = Addison-Wesley | location = Boston | year = 2000 | isbn = 0-201-44124-1 | edition = 2nd }} |
|||
* 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 [https://cs.brown.edu/courses/cs101/files/doc/fall2020/Lecture-17-NP%20and%20CoNP.pdf CS1010: Theory of Computation. Lecture 17: On NP vs CoNP, More examples of NP-Hard problems] brown.edu |
|||
* Chandra Chekuri, Fall 2010 [https://courses.engr.illinois.edu/cs473/fa2010/Lectures/lecture24.pdf CS 473: Algorithms] University of Illinois, Urbana-Champaign |
|||
== Посилання == |
|||
* [https://stackoverflow.com/questions/17046440/whats-the-difference-between-np-and-co-np Whats the difference between NP and co-NP] 2014y. |
|||
* [https://www.geeksforgeeks.org/types-of-complexity-classes-p-np-conp-np-hard-and-np-complete/ Types of Complexity Classes | P, NP, CoNP, NP hard and NP complete] |
|||
{{Мало джерел|дата=червень 2023}} |
|||
{{Класи складності}} |
|||
{{comp-sci-stub}} |
|||
[[Категорія:Класи складності]] |
[[Категорія:Класи складності]] |
||
[[Категорія:Теорія алгоритмів]] |
[[Категорія:Теорія алгоритмів]] |
||
[[Категорія:Нерозв'язані проблеми інформатики]] |
|||
[[de:Co-NP]] |
|||
[[en:Co-NP]] |
|||
[[es:Co-NP]] |
|||
[[he:Co-NP]] |
|||
[[it:Co-NP]] |
|||
[[ja:Co-NP]] |
|||
[[ko:Co-NP]] |
|||
[[pl:Klasa Co-NP]] |
|||
[[ru:Класс co-NP]] |
|||
[[zh:反NP]] |
|||
{{Ізольована стаття}} |
Поточна версія на 10:36, 2 червня 2023
У цій статті відсутні розділи за темами. (червень 2023) |
В теорії складності обчислень, 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
Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. (червень 2023) |
|
Це незавершена стаття з інформатики. Ви можете допомогти проєкту, виправивши або дописавши її. |