Pseudo-polynomial Time
   HOME

TheInfoList



OR:

In
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, a numeric algorithm runs in pseudo-polynomial time if its running time is a
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
in the ''numeric value'' of the input (the largest integer present in the input)—but not necessarily in the ''length'' of the input (the number of bits required to represent it), which is the case for
polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
algorithms.
Michael R. Garey Michael Randolph Garey (born November 19, 1945) is a computer science researcher, and co-author (with David S. Johnson) of ''Computers and Intractability: A Guide to the Theory of NP-completeness''. He and Johnson received the 1979 Frederick W. ...
and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length. An
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
problem with known pseudo-polynomial time algorithms is called weakly NP-complete. An
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
problem is called
strongly NP-complete In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general computational problem may have numerical parameters. For example, the input to the bin packing proble ...
if it is proven that it cannot be solved by a pseudo-polynomial time algorithm unless . The strong/weak kinds of
NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
ness are defined analogously.


Examples


Primality testing

Consider solving the problem of testing whether a number ''n'' is prime by naively checking whether a number in divides n evenly. This approach can take up to divisions, which is sub-linear in the ''value of n'' but exponential in the ''length of n'' (which is about \log(n)). For example, a number ''n'' slightly less than would require up to approximately 100,000 divisions, even though the length of ''n'' is only 11 digits. Moreover one can easily write down an input (say, a 300-digit number) for which this algorithm is impractical. Since computational complexity measures difficulty with respect to the ''length'' of the (encoded) input, this naive algorithm is actually exponential. It ''is'', however, pseudo-polynomial time. Contrast this algorithm with a true polynomial numeric algorithm—say, the straightforward algorithm for addition: Adding two 9-digit numbers takes around 9 simple steps, and in general the algorithm is truly linear in the length of the input. Compared with the actual numbers being added (in the billions), the algorithm could be called "pseudo-logarithmic time", though such a term is not standard. Thus, adding 300-digit numbers is not impractical. Similarly, long division is quadratic: an ''m''-digit number can be divided by a ''n''-digit number in O(mn) steps (see
Big O notation Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
.) In the case of primality, it turns out there is a different algorithm for testing whether ''n'' is prime (discovered in 2002) that runs in time O((\log )^6).


Knapsack problem

In the
knapsack problem The knapsack problem is the following problem in combinatorial optimization: :''Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given lim ...
, we are given n items with weight w_i and value v_i, along with a maximum weight capacity of a knapsack W. The goal is to solve the following optimization problem; informally, what's the best way to fit the items into the knapsack to maximize value? : maximize \sum_^n v_i x_i : subject to \sum_^n w_i x_i \leq W and x_i \in \. Solving this problem is
NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
, so a polynomial time algorithm is impossible unless . However, an O(nW) time algorithm is possible using dynamic programming; since the number W only needs \log W bits to describe, this algorithm runs in pseudo-polynomial time.


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 In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative int ...
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 polynomial problems a special case by taking ''k'' to be the numeric value 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''. {{Strong and weak NP hardness


See also

*
Strongly NP-complete In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general computational problem may have numerical parameters. For example, the input to the bin packing proble ...
* Quasi-polynomial time


References

Analysis of algorithms Complexity classes Computational complexity theory Pseudo-polynomial time algorithms