Pseudo-polynomial Time - Generalizing To Non-numeric Problems

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)