Computability theory is concerned with identifying one particular class of problems for which no "effective" algorithm exists. In general, problems of this nature have what is known as "exponential complexity" or "factorial complexity."

Algorithms have "exponential complexity" if they have running times that are determined by the size of the input being an exponent to a constant. In big-O notation, which is a theoretical measure of the algorithm's complexity, this is

• t(n) = O(kⁿ)

where k is a constant and ⁿ is the size of the input.

Problems have "factorial complexity" if the running time increases as a factorial of the input. The factorial of a number is given by multiplying it by all of the numbers that precede it. For example, "factorial 5," denoted by 5!, is 1 x 2 x 3 x 4 x 5 = 120. In big-O notation factorial complexity is denoted by

• t(n) = O(n!)

Algorithms that have either...