np time

1 definition found

np time - Free On-line Dictionary of Computing (26 May 2007) :

  nondeterministic polynomial time
  NP time
  
     <complexity> (NP) A set or property of computational decision problems
      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)