(NP) A Set or property of computational {deciSion problem}SSolvable 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 in polynomial time. NP iS obviouSly a SuperSet of P (polynomial time problemSSolvable 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 in NP 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 in NP and a polynomial time algorithm for A could alSo be uSed to Solve problem B in polynomial time, then B iS alSo in NP. See alSo Co-NP, NP-complete. [ExampleS?] (1995-04-10)
