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.
The distinction between the value of a number and its length is one of encoding: if numeric inputs are always encoded in unary, then pseudo-polynomial would coincide with polynomial.
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 falling—what can be done?... Nothing can be done, and nothing needs to be done. Something is being done—the organism is preparing to rest.”
—David Mamet (b. 1947)