Co-NP-komplet klasse

Co-NP-komplet problem  - i teorien om algoritmer , et problem med svaret "ja" eller "nej" , der tilhører klassen co-NP , sådan at ethvert problem fra denne klasse kan reduceres til det i polynomisk tid .

Hvis P ≠ co-NP, så kan intet co-NP-komplet problem løses i polynomiel tid. Hvis ethvert co-NP-komplet problem kan løses hurtigt , eksisterer der en hurtig algoritme for ethvert problem fra co-NP-klassen.

Ethvert co-NP-komplet problem er komplementet til et eller andet NP-komplet problem . Der er problemer, der hører til både NP -klassen og co-NP-klassen , såsom ethvert problem fra klasse P og faktoriseringsproblemet . Samtidig vides det ikke, om klasserne NP og co-NP er sammenfaldende eller tilsvarende, om der eksisterer et problem, der er både NP- og co-NP-komplet.

Formel definition

Et løselighedsproblem er co-NP-komplet, hvis det selv tilhører klassen co-NP, og ethvert andet co-NP-problem kan polynomielt reduceres til det. Med andre ord, for ethvert problem fra co-NP-klassen er der en algoritme, der i polynomisk tid transformerer inputdata for problemet til inputdata for problemet på en sådan måde, at svaret på det nye problem falder sammen. med svaret på den originale. Derfor, hvis der er en polynomiel algoritme for et problem, så kan ethvert problem fra co-NP-klassen løses i polynomiel tid.

Eksempel

Et simpelt eksempel på et co-NP-komplet problem er at teste en boolsk formel for tautologi . Det vil sige, om den givne formel er sand for alle sæt af variabler. Dette problem er tæt forbundet med tilfredshedsproblemet , hvor vi skal finde ud af, om der findes mindst et sådant sæt af variabler.

Litteratur

• Cormen T. Leizerson C. Rivest R. Algoritmer: Konstruktion og analyse: Lærebog: pr. fra engelsk. . — Moskva MTsNMO. Arkiveret 21. august 2019 på Wayback Machine