Home

Pseudopolynomial

Pseudopolynomial time is a concept in computational complexity describing algorithms whose running time is polynomial in the numeric value of the input rather than in the length of the input encoding. In other words, the time bound is polynomial in numbers that appear in the instance (such as weights, capacities, or costs). Because the numeric values may require many digits to represent, a pseudopolynomial-time algorithm can be exponential in the input size even though it is polynomial in the data values.

A classic setting involves problems with numeric parameters. For example, the knapsack problem can be solved

The distinction between pseudopolynomial time and true polynomial time depends on the encoding of numbers. Pseudopolynomial

Overall, pseudopolynomial time highlights a boundary between tractable behavior for certain parameter ranges and intractability under

by
dynamic
programming
in
O(nW)
time,
where
n
is
the
number
of
items
and
W
is
the
capacity.
The
subset
sum
and
partition
problems
also
admit
pseudopolynomial-time
solutions
in
terms
of
the
sum
of
the
input
numbers.
These
problems
are
often
described
as
weakly
NP-hard:
if
the
numbers
are
encoded
in
unary
(so
input
length
grows
with
the
values),
the
pseudopolynomial
algorithm
becomes
polynomial-time
in
the
input
size.
algorithms
are
polynomial
in
the
magnitude
of
the
numeric
data
but
not
necessarily
in
the
length
of
the
input
encoding
(which
is
typically
proportional
to
the
logarithm
of
the
numbers).
If
all
numbers
are
small
or
encoded
in
unary,
pseudopolynomial-time
algorithms
may
effectively
run
in
polynomial
time
with
respect
to
input
size;
with
binary
encoding,
they
may
be
exponential
in
input
length.
standard
input
encodings,
and
it
is
closely
associated
with
the
notion
of
weakly
NP-hard
problems.