non-polynomial


non-polynomial

(complexity)The set or property of problems for which nopolynomial-time algorithm is known.

This includes problems for which the only known algorithmsrequire a number of steps which increases exponentially withthe size of the problem, and those for which no algorithm atall is known. Within these two there are problems which are"provably difficult" and "provably unsolvable".