Co-NP-komplett klass

Co-NP-komplett problem  - i teorin om algoritmer , ett problem med svaret "ja" eller "nej" , som tillhör klassen co-NP , så att alla problem från denna klass kan reduceras till det i polynomtid .

Om P ≠ co-NP, så kan inget co-NP-komplett problem lösas i polynomtid. Om något co-NP-komplett problem kan lösas snabbt , så finns det en snabb algoritm för alla problem från co-NP-klassen.

Varje co-NP-komplett problem är komplementet till något NP-komplett problem . Det finns problem som tillhör både NP -klassen och co-NP-klassen , till exempel alla problem från klass P och faktoriseringsproblemet . Samtidigt är det inte känt om klasserna NP och co-NP sammanfaller eller, motsvarande, om det finns ett problem som är både NP- och co-NP-komplett.

Formell definition

Ett lösbarhetsproblem är co-NP-komplett om det självt tillhör klassen co-NP och alla andra co-NP-problem är polynomiellt reducerbara till det. Med andra ord, för alla problem från co-NP-klassen finns det en algoritm som i polynomtid transformerar indata för problemet till indata för problemet på ett sådant sätt att svaret på det nya problemet sammanfaller med svaret på originalet. Därför, om det finns en polynomalgoritm för ett problem, kan alla problem från co-NP-klassen lösas i polynomtid.

Exempel

Ett enkelt exempel på ett co-NP-komplett problem är att testa en boolesk formel för tautologi . Det vill säga om den givna formeln är sann för alla uppsättningar av variabler. Detta problem är nära relaterat till tillfredsställbarhetsproblemet , där vi måste ta reda på om det finns minst en sådan uppsättning variabler.

Litteratur

• Cormen T. Leizerson C. Rivest R. Algoritmer: Konstruktion och analys: Lärobok: per. från engelska. . — Moskva MTsNMO. Arkiverad 21 augusti 2019 på Wayback Machine