# Wikipedia Authors - NP (Complexity) (Highlights) ![rw-book-cover|256](https://readwise-assets.s3.amazonaws.com/static/images/article2.74d541386bbf.png) ## 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