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:
“I was a wonderful parent before I had children. I was an expert on why everyone else was having problems with theirs. Then I had three of my own.”
—Adele Faber (20th century)