In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms.
An NP-complete problem is called strongly NP-complete if it is proven that it cannot be solved by a pseudo-polynomial time algorithm unless P = NP.
For example, a number n slightly less than 10,000,000,000 would require up to approximately 100,000 divisions, even though the length of n is only 11 digits.
Moreover one can easily write down an input (say, a 300-digit number) for which this algorithm is impractical.
Since computational complexity measures difficulty with respect to the length of the (encoded) input, this naive algorithm is actually exponential.
Contrast this algorithm with a true polynomial numeric algorithm—say, the straightforward algorithm for addition: Adding two 9-digit numbers takes around 9 simple steps, and in general the algorithm is truly linear in the length of the input.
Compared with the actual numbers being added (in the billions), the algorithm could be called "pseudo-logarithmic time", though such a term is not standard.
In the case of primality, it turns out there is a different algorithm for testing whether n is prime (discovered in 2002) that runs in time
The goal is to solve the following optimization problem; informally, what's the best way to fit the items into the knapsack to maximize value?
Solving this problem is NP-hard, so a polynomial time algorithm is impossible unless P = NP.
time algorithm is possible using dynamic programming; since the number
bits to describe, this algorithm runs in pseudo-polynomial time.
Although the notion of pseudo-polynomial time is used almost exclusively for numeric problems, the concept can be generalized: The function m is pseudo-polynomial if m(n) is no greater than a polynomial function of the problem size n and an additional property of the input, k(n).
Assuming P ≠ NP, the following are true for computational problems on integers:[2]