The Collaborative International Dictionary
Np \Np\ n. The chemical symbol for Neptunium, a transuranic element having atomic number 93.
Syn: Neptunium, atomic number 93.
abbr. 1 (context text messaging Internet English) no problem; it was nothing; it's ok; don't mention it; you're welcome. 2 no pagination 3 no place (of publication)
In computational complexity theory, NP is a complexity class used to describe certain types of decision problems. Informally, NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs. More precisely, these proofs have to be verifiable by deterministic computations that can be performed in polynomial time.
Equivalently, the formal definition of NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine. This second definition is the basis for the abbreviation NP, which stands for " nondeterministic, polynomial time." However, the verifier-based definition tends to be more intuitive and practical in common applications compared to the formal machine definition. The two definitions are equivalent because the algorithm for the machine definition consists of two phases, the first of which consists of a guess about the solution, which is generated in a non-deterministic way, while the second phase consists of a deterministic algorithm that verifies or rejects the guess as a valid solution to the problem.
A method for solving a decision problem is given in the form of an algorithm. In the above definitions for NP, polynomial time refers to the increasing number of machine operations needed by an algorithm relative to the size of the problem. Polynomial time is therefore a measure of efficiency of an algorithm. Decision problems are commonly categorized into complexity classes (such as NP) based on the fastest known machine algorithms. As such, decision problems may change class if a faster algorithm is discovered.
The complexity class P is contained in NP, but NP contains many important problems, the hardest of which are called NP-complete problems, whose solutions are sufficient to deal with any other NP problem in polynomial time. The most important open question in complexity theory, the P versus NP ("P=NP") problem, asks whether polynomial time algorithms actually exist for solving NP-complete, and by corollary, all NP problems. It is widely believed that this is not the case.
The complexity class NP (which have efficiently verifiable proofs where the answer is "yes") is also related to the complexity class co-NP (which have efficiently verifiable proofs where the answer is "no"). Whether or not NP = co-NP is another outstanding question in complexity theory.
NP may refer to:
Usage examples of "np".
Since several nations were still trying to obtain them, the extension of NPT was one of my most important nonproliferation objectives.
His long arms, encased in NPS green, semaphored information and enthusiasm.
NPT, possibly because the polo and sports car afficionado with the posh accent lacks the diplomatic gloss appropriate to this sensitive enterprise.
Muscular hips and legs gave her a stocky silhouette that was accentuated by the flat-brimmed hat and cloddy shoes of the NPS uniform she wore on duty.