Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

У цій статті відсутні розділи за темами Ви можете допомогти розбивши тематично пов язані частини статті на розділи для п

Co-NP

Co-NP
У цій статті відсутні . Ви можете допомогти, розбивши тематично пов'язані частини статті на розділи для покращення читацького сприйняття. (червень 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 .
  • 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
  • LorenzoDeStefani. Fall, 2020 CS1010:TheoryofComputation. Lecture17:On NP vs CoNP, More examples ofNP-Hardproblems 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)
image Це незавершена стаття з інформатики.
Ви можете проєкту, виправивши або дописавши її.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

U cij statti vidsutni rozdili za temami Vi mozhete dopomogti rozbivshi tematichno pov yazani chastini statti na rozdili dlya pokrashennya chitackogo sprijnyattya cherven 2023 V teoriyi skladnosti obchislen co NP klas skladnosti Zadacha nalezhit klasu co NP todi i tilki todi koli komplanarna do neyi zadacha nalezhit klasu NP Neformalno co NP klas zadach dlya yakih isnuyut efektivni polinomialnoyi skladnosti pereviryuvachi dlya vidpovidi Ni Vizmemo priklad NP povnoyi zadachi pro sumu pidmnozhin Dana skinchenna mnozhina cilih chisel Chi ye u neyi hoch odna neporozhnya pidmnozhina suma elementiv yakoyi rivna nulyu Komlanarnoyu do ciyeyi zadachi bude taka Dana skinchenna mnozhina cilih chisel Chi kozhna neporozhnya maye nenulovu sumu elementiv Shob dovesti vidpovid Ni mayemo nadati yakus neporozhnyu pidmnozhinu suma elementiv yakoyi rivna nulyu Take dovedennya legko pereviriti za polinomialnij chas P klas zadach rozv yaznih za polinomialnij chas ye pidmnozhinoyu yak NP tak i co NP NP i co NP vvazhayutsya hoch ce ne dovedeno nerivnimi Yaksho dlya yakoyi nebud NP povnoyi zadachi dovesti sho vona nalezhit klasu co NP to ce oznachalo b rivnist cih klasiv Oskilki bud yaka NP zadacha za oznachennyam zvoditsya do NP povnoyi za polinomialnij chas Zadacha sho nalezhit yak do NP tak i do co NP dosit jmovirno za pripushennyam pro nerivnist cih klasiv ne ye NP povnoyu Prikladom zadachi sho nalezhit yak do NP tak i do co NP ye faktorizaciya chisla dano naturalni chisla m ta n Viznachiti chi m maye prostij dilnik menshij za n Nalezhnist do NP ochevidna yaksho m maye takij dilnik to vin i ye pidtverdzhennyam vidpovidi Dovedennya nalezhnosti do co NP skladnishe dlya perevirki vidpovidi mayemo perelichiti prosti dilniki m ta dovesti dlya kozhnogo sho vin ye prostim Insha zadacha z peretinu NP co NP perevirka chi ye chislo prostim LiteraturaHopcroft John E 2000 Introduction to Automata Theory Languages and Computation vid 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 LorenzoDeStefani Fall 2020 CS1010 TheoryofComputation Lecture17 On NP vs CoNP More examples ofNP Hardproblems brown edu Chandra Chekuri Fall 2010 CS 473 Algorithms University of Illinois Urbana ChampaignPosilannyaWhats the difference between NP and co NP 2014y Types of Complexity Classes P NP CoNP NP hard and NP completeCya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno cherven 2023 Ce nezavershena stattya z informatiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi

Дата публікації:
Топ