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 proper method of philosophy consists in clearly conceiving the insoluble problems in all their insolubility and then in simply contemplating them, fixedly and tirelessly, year after year, without any hope, patiently waiting.”
—Simone Weil (1909–1943)