It means that the algorithm is polynomial with respect to the size of the input, but the input actually grows exponentially.
For example take the subset sum problem. We have a set S
of n
integers and we want to find a subset which sums up to t
.
To solve this problem you can just check the sum of each subset, so it is O(P) where P is the number of subsets. However in fact the number of subsets is 2^n so the algorithm has exponential complexity.
I hope this introduction helps to understand the wikipedia's article about it http://en.wikipedia.org/wiki/Pseudo-polynomial_time :)