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.
随便看	ctesias ctesias of cnidus ctesibius ctesibius of alexandria ctesiphon ctesl ctess ctest ctet ctetology ctev ctevh ctevt cmkbr3 cmkbr4 cmkbr5 cmkbr6 cmkbr7 cmkbr8 cmk-brl-1 cmk-brl1 cmkbrl1 cmkbrl2 cmkd cmkdr1