nondeterministic polynomial time

(complexity)(NP) A set or property of computational decision problems solvable by a nondeterministic Turing Machine in anumber of steps that is a polynomial function of the size ofthe input. The word "nondeterministic" suggests a method ofgenerating potential solutions using some form ofnondeterminism or "trial and error". This may takeexponential time as long as a potential solution can beverified 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 adegenerate form of nondeterministic algorithm. The questionthen arises: is NP equal to P? I.e. can every problem in NPactually be solved in polynomial time? Everyone's first guessis "no", but no one has managed to prove this; and some veryclever people think the answer is "yes".

If a problem A is in NP and a polynomial time algorithm for Acould also be used to solve problem B in polynomial time, thenB is also in NP.

See also Co-NP, NP-complete.

单词	nondeterministic polynomial time
释义	nondeterministic polynomial time nondeterministic polynomial time (complexity)(NP) A set or property of computational decision problems solvable by a nondeterministic Turing Machine in anumber of steps that is a polynomial function of the size ofthe input. The word "nondeterministic" suggests a method ofgenerating potential solutions using some form ofnondeterminism or "trial and error". This may takeexponential time as long as a potential solution can beverified 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 adegenerate form of nondeterministic algorithm. The questionthen arises: is NP equal to P? I.e. can every problem in NPactually be solved in polynomial time? Everyone's first guessis "no", but no one has managed to prove this; and some veryclever people think the answer is "yes". If a problem A is in NP and a polynomial time algorithm for Acould also be used to solve problem B in polynomial time, thenB is also in NP. See also Co-NP, NP-complete.
随便看	kellett, henry kelley, abby kelley blue book kelley business education network kelley, edgar stillman kelley, edward kelley, emmett kelley engineering center kelley, florence kelley, francis clement kelley habib john kelley, hall j. kelley, hall jackson kelley index of malignancy kelley international perspectives kelley manufacturing co. kelley, mike kelley, oliver hudson isocheimal isocheimenal isocheimic isocheims isochela isochemical metamorphism isochemical series