provably difficult The set or property of problems for which it can be proven that no {polynomial-time} {algorithm} exists, only {exponential-time} {algorithms}.