Statements (35)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:abbreviation |
gptkb:coNP
complement of NP |
| gptkbp:complement |
NP
|
| gptkbp:contains |
gptkb:TAUT
gptkb:UNSAT |
| gptkbp:definedIn |
decision problems whose complement is in NP
problems whose complement is in NP |
| gptkbp:describedBy |
gptkb:Cook-Levin_theorem
|
| gptkbp:hasSubgroup |
gptkb:PSPACE
|
| https://www.w3.org/2000/01/rdf-schema#label |
coNP
|
| gptkbp:introducedIn |
gptkb:complexity_theory
|
| gptkbp:isClosedUnder |
gptkb:intersection
Union complement polynomial-time many-one reductions polynomial-time reductions |
| gptkbp:isNotKnownToEqual |
P
NP coNP-complete |
| gptkbp:level |
polynomial hierarchy
|
| gptkbp:numberOfIssues |
gptkb:TAUT
gptkb:UNSAT Graph non-3-colorability Non-Hamiltonian graph Non-primality (historically, before PRIMES in P) |
| gptkbp:openQuestion |
NP vs coNP
|
| gptkbp:partOf |
polynomial hierarchy
|
| gptkbp:relatedTo |
gptkb:PSPACE
P PH NP-complete |
| gptkbp:symbol |
gptkb:coNP
|
| gptkbp:bfsParent |
gptkb:P/poly
|
| gptkbp:bfsLayer |
6
|