Вікіпедія

Клас складності co-NP: відмінності між версіями

Інтерактивний перегляд історії
[неперевірена версія][неперевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
+ {{Ізольована стаття}} за допомогою AWB
Немає опису редагування
Рядок 1:
{{Статті, з яких нема посилань}}
В теорії складності обчислень, [[co-NP]] - клас складності. Задача належить класу co-NP тоді і тільки тоді, коли компланарна до неї задача належить [[Клас складності NP|класу NP]]. Неформально, co-NP – клас задач, для яких існують ефективні (поліноміальної складності) перевірювачі для відповіді «Ні» .▼
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 andта n . Визначити, чи m має [[просте число|простий]] [[дільник ]], менший за n. Належність до NP очевидна: якщо m має такий дільник, то він і є підтвердженням відповіді. Доведення належності до co-NP складніше: для перевірки відповіді маємо перелічити прості дільники m та довести для кожного, що він є простим. Інша задача з перетину NP ∩ co-NP – перевірка чи є число [[просте число|простим]].
 
{{rq|src|wikify}}
 
[[Категорія:Теорія алгоритмів]]
 
Отримано з https://uk.wikipedia.org/wiki/Клас_складності_co-NP