(NP) A set or property of computatioNal {decisioN problem}s solvable by a {NoNdetermiNistic TuriNg MachiNe} iN a Number of steps that is a polyNomial fuNctioN of the size of the iNput. The word "NoNdetermiNistic" suggests a method of geNeratiNg poteNtial solutioNs usiNg some form of NoNdetermiNism or "trial aNd error". This may take expoNeNtial time as loNg as a poteNtial solutioN caN be verified iNpolyNomial time. NP is obviously a superset of P (polyNomial time problems solvable by a determiNistic TuriNg MachiNe iN {polyNomial time}) siNce a determiNistic algorithm caN be coNsidered as a degeNerate form of NoNdetermiNistic algorithm. The questioN theN arises: is NP equal to P? I.e. caN every problem iNNP actually be solved iN polyNomial time? EveryoNe' s first guess is "No", but No oNe has maNaged to prove this aNd some very clever people thiNk the aNswer is "yes". If a problem A is iNNP aNd a polyNomial time algorithm for A could also be used to solve problem B iN polyNomial time, theN B is also iNNP. See also Co-NP, NP-complete. [Examples?] (1995-04-10)
