Advanced Algorithms (Winter 2026-27) - 03-01 Pseudopolynomial algorithms

Overview

Sebastian Wild defines integer input problems and uses the largest encoded integer, max int, to explain pseudopolynomial running time: polynomial in both input length and max int. Because a binary-encoded integer can be exponential in the input length, pseudopolynomial time is not generally polynomial time, but it becomes polynomial on instances whose max int is polynomially bounded. He formalizes this through restricted problem instances and shows the same implication for optimization problems.

Key takeaways

Pseudopolynomial running time is polynomial in the input length and the magnitude of the largest encoded integer, not just in the number of input bits.
A binary-encoded integer may be exponential in its encoding length, so a polynomial dependence on max int can still produce exponential running time on unrestricted inputs.
For integer input problems such as Subset Sum, Bin Packing, TSP with distances, integer linear programming, and Knapsack, the largest integer provides a useful second measure of instance size.
If max int is bounded by a polynomial in the input length, substituting that bound into a pseudopolynomial runtime produces an ordinary polynomial runtime.
A pseudopolynomial algorithm therefore solves the polynomially bounded-integer restriction of its problem in polynomial time, including the corresponding restricted optimization problem.

Chapters

0:00 Integer Input Problems and the Exponential Range of Binary Values

An integer input problem is one whose instance semantically involves a sequence of integers, such as Subset Sum, Bin Packing, TSP with distances, integer linear programming, or Knapsack.
Define max int as the absolute value of the largest integer in an instance; assume sensible binary encoding so values are not artificially inflated by their representation.
With an input encoding of N bits, max int can be exponential in N, since the entire input could encode one large number.

8:05 Pseudopolynomial Time and Its Difference from Quasipolynomial Time

An algorithm is pseudopolynomial when its running time is polynomial in both the encoding length and max int, for example, a runtime proportional to max int raised to the tenth power.
Since max int can be exponential in the input length, a pseudopolynomial bound does not guarantee ordinary polynomial time for unrestricted instances.
Quasipolynomial time is a separate growth class, typically written as 2 to the poly(log n); n to the log n is an example, unlike pseudopolynomial time.

10:09 Polynomially Bounded Integers Yield Polynomial-Time Algorithms

The H-restriction of a problem includes only instances whose max int is at most H of the encoding length.
If H is polynomial and an algorithm runs in time polynomial in input length and max int, substituting the bound on max int gives a polynomial-time algorithm for the restricted problem.
The same reasoning applies to optimization problems: a pseudopolynomial algorithm yields a polynomial-time algorithm on instances with polynomially bounded max int, placing that restricted version in PO.

Transcript excerpt

0:02 Let us recap where we are. We've now covered again classic complexity theory, which is pretty much about bad news. We've covered these four pages of different interesting problems that model all sorts of um abstracted as versions of of real-life problems, and they're all NP-complete. So, what do we do next? And the first of these loopholes that I promised we'll look at uh is essentially using um then pseudo-polynomial time algorithms, which is a term you if you've not heard of doesn't help that much. Um it looks at a specific property of of these problems that they sometimes have, which is namely being defined in terms of

0:50 numbers. And if these numbers aren't too big, sometimes uh the problem is not that bad to solve. Now, we'll see an example of that. And also the limits, um let's start a bit with uh making a bit more formal, a bit more clear what we mean when we talk about this um integer-based problems. Um I call these integer input problems, where this this language that we care about is again you know, there's encodings for all valid valid problems, and then there's the yes instances. We're back to the threshold worlds, where we just decide a yes or a no. And if this input uh semantically means there is a

1:38 sequence of integers behind it or involved, then let's call this an integer input problem. This is a bit of an informal definition, because it really is a semantic distinction. My point is here rather to make sure that we we uh define the scope of what's to come. For these problems, let's use this uh notation max int to just decode mean the modulus of the largest integer that occurs in this encoding. I think here if there's negative numbers

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

In this course

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Sebastian Wild (Lectures).