# Wikipedia Authors - NP (Complexity) (Highlights)

## Metadata
**Cover**:: <https://readwise-assets.s3.amazonaws.com/static/images/article2.74d541386bbf.png>
**Source**:: #from/readwise
**Zettel**:: #zettel/fleeting
**Status**:: #x
**Authors**:: [[Wikipedia Authors]]
**Full Title**:: NP (Complexity)
**Category**:: #articles #readwise/articles
**Category Icon**:: 📰
**Document Tags**:: #computer-science
**URL**:: [en.wikipedia.org](https://en.wikipedia.org/wiki/NP_(complexity)?oldformat=true)
**Host**:: [[en.wikipedia.org]]
**Highlighted**:: [[2020-02-06]]
**Created**:: [[2022-09-26]]
## Highlights
- NP is the [set](https://en.wikipedia.org/wiki/Set_(mathematics) "Set (mathematics)") of decision problems for which the [problem instances](https://en.wikipedia.org/wiki/Computational_complexity_theory#Problem_instances "Computational complexity theory"), where the answer is "yes", have [proofs](https://en.wikipedia.org/wiki/Mathematical_proof "Mathematical proof") verifiable in [polynomial time](https://en.wikipedia.org/wiki/Polynomial_time "Polynomial time") by a [deterministic Turing machine](https://en.wikipedia.org/wiki/Deterministic_Turing_machine "Deterministic Turing machine").
There exists a verifier which can checks a solution is correct in polynomial time.
- the complexity class [co-NP](https://en.wikipedia.org/wiki/Co-NP "Co-NP") for which the answer "no" can be verified in polynomial time.
Verifier which checks the answer is wrong in polynomial time