Definition
In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly.
Related concepts
2-EXPTIMEAC0ACC0ALL (complexity)APXArithmetical hierarchyArthur–Merlin protocolBPP (complexity)BQPBoolean algebra (logic)Boolean hierarchyBoolean satisfiability problemCC (complexity)Co-NPComplexity ZooComplexity classComputational complexity theoryDLOGTIMEDSPACEDTIMEDecision problemELEMENTARYEXPSPACEEXPTIMEExponential hierarchyFL (complexity)FNP (complexity)FP (complexity)Grzegorczyk hierarchyIP (complexity)Interactive proof systemL (complexity)List of complexity classesMahaney's theoremNC (complexity)NEXPTIMENL-completeNL (complexity)NONELEMENTARYNP-completeNP-completenessNP-hardnessNP (complexity)NSPACENTIMEP-completePP (complexity)PR (complexity)PSPACEPSPACE-completeP (complexity)P = NP problemParity PPolyLPolynomial-time many-one reductionPolynomial hierarchyProbabilistically checkable proofQMAQuasi-polynomial timeRE (complexity)RL (complexity)RP (complexity)R (complexity)Regular languageSC (complexity)SL (complexity)Sparse languageTC0TC (complexity)TFNPTautology (logic)Truth valueUP (complexity)ZPP (complexity)♯P♯P-complete
7 concepts already in your glossary