Az elméleti számítógép-tudomány , coNP (vagy coNP ) egy osztály a komplexitás , azaz egy sor döntési problémák értelmében komplexitás elmélet . Ez az NP osztály komplex osztálya (a komplexitás értelmében) .
Két egyenértékű definíciót adunk meg.
a co-NP azon nyelvek összessége, amelyek kiegészítik (a nyelvek értelmében) az NP nyelvét .
A látás másik módja az, hogy a co-NP az a nyelvkészlet, amelyre egy polinomiális időben ellenőrizhető bizonyíték igazolni tudja, hogy a szó nem tartozik a nyelvhez (ellenpéldák).
A coNP osztályt tanúsítványok segítségével határozhatja meg . Ábécén a nyelv co-NP-ben van, ha polinom és Turing-gép létezik polinomiális időben , oly módon, hogy egy szóra ekvivalencia van és az a tény, hogy bármely tanúsítvány esetében a gép elfogadja a bejegyzést .
Ami az NP osztályt illeti, meghatározzuk a co-NP-nehéz problémák fogalmát . Egy probléma akkor nehéz együtt-NP, ha valamelyik NP-probléma polinomiális idő alatt csökken . Egy probléma együtt-NP-teljes, ha együtt-NP- ben van, és nehéz együtt-NP-vel.
Az NP bármely problémájából felépíthetünk egy „kettős” problémát a co-NP-ben.
Probléma az NP-ben | Kiegészítő probléma az coNP-ben |
---|---|
a SAT probléma : Boole-képletet figyelembe véve van-e olyan változók hozzárendelése, amely igazat tesz? | logikai képletet adott, hamis a változók bármilyen hozzárendeléséhez? (még akkor is, ha inkább az érvényesség problémáját vesszük figyelembe, amely az előző problémára átolvasható : Boole-képletet figyelembe véve igaz ez a változók összes hozzárendelésére?) |
a hamiltoni út problémája : adott egy G grafikon , létezik- e hamiltoni út? | a hamiltoni pálya nem létezésének problémája : adott n csomópontból és m ívből álló G grafikon , igaz-e, hogy n ív egyetlen kombinációja sem m alkotja a hamiltoni utat? |
A klikk probléma : adott egy gráf G és egy egész szám k , nem egy klikk méretű k léteznek a G ? | a nem klikkes probléma: adott egy G grafikon és egy k egész szám , igaz-e, hogy G-nek nincs k méretű klikkje ? |
A co-NP = NP kérdés nyitott kérdés, de feltételezhető, hogy ezek az osztályok különbözőek. Ha P = NP , akkor NP = co-NP, de fordítva nem ismert.
Tudjuk ezt , de az egyenlőség nyitott kérdés. A termék elsődleges tényezőjének bomlási problémája köztudottan NP-ben és co-NP-ben van, de általában úgy gondolják, hogy P-ben nem.
A polinomiális hierarchiában a co-NP megfelel az első egzisztenciális szakasznak: co-NP = .
A komplexitáselméletben azt mondják, hogy egy probléma ko-NP-teljes, ha co-NP, és ha bármely ko-NP probléma redukálható polinomiális időben . Más szóval, ez a teljes problémák osztálya, amely megfelel a co-NP-nek . Bármely co-NP-teljes probléma kiegészíti az NP-complete problémát.
en) Sanjeev Arora és Boaz Barak , Számítási bonyolultság: modern megközelítés , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , fej . 2.6 ("co-NP, EXP és NEXP")
(fr) Co-NP osztály a Komplexitás Állatkertben