Nonpolynomial

1 definition found

From The Free On-line Dictionary of Computing (27 SEP 03) [foldoc]:

  non-polynomial
       
           The set or property of problems for which no
          {polynomial-time algorithm} is known.
       
          This includes problems for which the only known {algorithm}s


          require a number of steps which increases exponentially with
          the size of the problem, and those for which no {algorithm} at
          all is known.  Within these two there are problems which are
          "{provably difficult}" and "{provably unsolvable}".
       
          (1995-04-10)