The complexity class of decision problems for which a proposed solution can be verified in polynomial time, even if no polynomial-time method for finding that solution in the first place is known; every problem in P is also in NP.
Facts
Core PrincipleThe set of decision problems whose yes-instances have proofs verifiable in polynomial time by a deterministic Turing machine, or equivalently that can be solved in polynomial time by a nondeterministic Turing machine. 1 Connections
Sources
1. NP (complexity), Wikipedia
Lead section, second sentenceQuote, Lead section, second sentence
NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.
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.