Generalizing To Non-numeric Problems
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). (Presumably, k is chosen to be something relevant to the problem.) This makes numeric problems a special case by taking k to be the number of (binary) digits of the input.
Read more about this topic: Pseudo-polynomial Time
Famous quotes containing the word problems:
“The problems of the world, AIDS, cancer, nuclear war, pollution, are, finally, no more solvable than the problem of a tree which has borne fruit: the apples are overripe and they are fallingwhat can be done?... Nothing can be done, and nothing needs to be done. Something is being donethe organism is preparing to rest.”
—David Mamet (b. 1947)