Со-НП

Определение co-NP
- co-NP — это класс задач, для которых существует алгоритм проверки сертификата за полиномиальное время.
- Задача X является членом co-NP, если дополнение X принадлежит NP.
Примеры и дополнительные задачи
- Задача логической выполнимости является NP-полной, а ее дополнение — задачей о невыполнимости.
- Задачи в NP и co-NP могут быть связаны через сокращение за полиномиальное время.
Связь с другими классами сложности
- P является подмножеством NP и co-NP, но считается строгим подмножеством в обоих случаях.
- NP и co-NP не обязательно эквивалентны, что приводит к противоречию в случае, если NP = co-NP.
Целочисленная факторизация
- Задача целочисленной факторизации известна как находящаяся в NP и co-NP, но не в P.
- Алгоритм разложения на множители, эквивалентный целочисленной факторизации в P, неизвестен.

Полный текст статьи:

со-НП