資料來源 : Free On-Line Dictionary of Computing

nondeterministic polynomial time
     
         (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 in {polynomial 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 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)