Клас складності co-NP: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
+ {{Ізольована стаття}} за допомогою AWB |
Deineka (обговорення | внесок) Немає опису редагування |
||
Рядок 1: | Рядок 1: | ||
{{Статті, з яких нема посилань}} |
{{Статті, з яких нема посилань}} |
||
⚫ | В теорії складності обчислень, [[co-NP]] - клас складності. Задача належить класу co-NP тоді і тільки тоді, коли компланарна до неї задача належить [[Клас складності NP|класу NP]]. Неформально, co-NP – клас задач, для яких існують ефективні (поліноміальної складності) перевірювачі для відповіді «Ні». |
||
Co-NP |
|||
⚫ | |||
Візьмемо приклад NP-повної задачі про суму підмножин: «Дана скінченна множина цілих чисел. Чи є у неї хоч одна непорожня підмножина, сума елементів якої рівна нулю?» Комланарною до цієї задачі буде така: «Дана скінченна множина цілих чисел. Чи кожна непорожня має ненульову суму елементів?» Щоб довести відповідь «Ні», маємо надати якусь непорожню підмножину, сума елементів якої рівна нулю. Таке доведення легко перевірити за поліноміальний час. |
Візьмемо приклад NP-повної задачі про суму підмножин: «Дана скінченна множина цілих чисел. Чи є у неї хоч одна непорожня підмножина, сума елементів якої рівна нулю?» Комланарною до цієї задачі буде така: «Дана скінченна множина цілих чисел. Чи кожна непорожня має ненульову суму елементів?» Щоб довести відповідь «Ні», маємо надати якусь непорожню підмножину, сума елементів якої рівна нулю. Таке доведення легко перевірити за поліноміальний час. |
||
P, клас задач, розв’язних за поліноміальний час ,є підмножиною як NP так і co-NP. |
P, клас задач, розв’язних за поліноміальний час ,є підмножиною як NP так і co-NP. |
||
NP і co-NP вважаються (хоч це не доведено) нерівними. Якщо для якої-небудь NP-повної задачі довести, що вона належить класу co-NP, то це означало б рівність цих класів. Так як будь-яка NP-задача (за означенням) зводиться до NP-повної за поліноміальний час. |
NP і co-NP вважаються (хоч це не доведено) нерівними. Якщо для якої-небудь NP-повної задачі довести, що вона належить класу co-NP, то це означало б рівність цих класів. Так як будь-яка NP-задача (за означенням) зводиться до NP-повної за поліноміальний час. |
||
Задача, що належить як до NP ,так і до co-NP, досить ймовірно(за припущенням про нерівність цих класів) не є NP-повною. |
Задача, що належить як до NP ,так і до co-NP, досить ймовірно(за припущенням про нерівність цих класів) не є NP-повною. |
||
Прикладом задачі, що належить як до NP ,так і до co-NP, є факторизація числа: «дано натуральнї числа m |
Прикладом задачі, що належить як до NP ,так і до co-NP, є факторизація числа: «дано [[натуральнї числа]] m та n. Визначити, чи m має [[просте число|простий]] [[дільник]], менший за n. Належність до NP очевидна: якщо m має такий дільник, то він і є підтвердженням відповіді. Доведення належності до co-NP складніше: для перевірки відповіді маємо перелічити прості дільники m та довести для кожного, що він є простим. Інша задача з перетину NP ∩ co-NP – перевірка чи є число [[просте число|простим]]. |
||
{{rq|src|wikify}} |
|||
[[Категорія:Теорія алгоритмів]] |
[[Категорія:Теорія алгоритмів]] |
||
Версія за 05:47, 30 вересня 2009
Ця стаття не містить посилань на інші статті Вікіпедії. |
В теорії складності обчислень, 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 – перевірка чи є число простим.
Ця стаття має кілька недоліків. Будь ласка, допоможіть удосконалити її або обговоріть ці проблеми на сторінці обговорення.
src
|
На цю статтю не посилаються інші статті Вікіпедії. Будь ласка розставте посилання відповідно до прийнятих рекомендацій. |