The complexity class of decision problems whose complement, the same problem with yes and no answers swapped, belongs to NP; equivalently, the class of problems for which a proposed NO answer can be verified in polynomial time.
Facts
Core PrincipleA decision problem belongs to co-NP if and only if its complement belongs to NP. 1 Connections
Sources
1. co-NP, Wikipedia
Lead section, second sentenceQuote, Lead section, second sentence
A decision problem X is a member of co-NP if and only if its complement
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.