< complexity > 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)