Advanced Algorithms (Winter 2026-27) - 03-04 Strong NP hardness

Overview

Sebastian Wild defines strong NP-hardness by requiring a problem to remain NP-hard when every integer in its input is bounded by a polynomial in the input length. Assuming P ≠ NP, this rules out pseudo-polynomial algorithms; Wild demonstrates the definition with a Hamiltonian-cycle reduction to TSP and explains its equivalence to NP-hardness under unary encoding.

Key takeaways

Strong NP-hardness means an NP-hard restriction persists even when every input integer is polynomially bounded by the input length.
If P ≠ NP, a strongly NP-hard problem cannot have a pseudo-polynomial-time algorithm, because the algorithm would run in polynomial time on the hard restricted instances.
The Hamiltonian Cycle reduction proves TSP strongly NP-hard using edge distances of 1, non-edge distances of 2, and tour threshold n.
A problem is strongly NP-hard exactly when its unary-encoded version is NP-hard; unary representation makes numeric magnitudes contribute directly to input length.
Knapsack's pseudo-polynomial dynamic program is polynomial under unary encoding, so the optimization problem can be solved optimally in polynomial time on those inputs.
Strict NP-hardness is a different concept from strong NP-hardness and concerns polynomially many arithmetic operations without accounting for number size.

Chapters

0:00 Strong NP-Hardness and the Barrier to Pseudo-Polynomial Algorithms

A problem is strongly NP-hard if restricting instances so their maximum integer is at most some polynomial in input length still leaves an NP-hard problem.
If P ≠ NP, a pseudo-polynomial algorithm for a strongly NP-hard problem would become polynomial-time on that restricted set of instances, contradicting NP-hardness.
For decision problems, Wild denotes all valid inputs by L and yes-instances by Y, and distinguishes strong NP-hardness from the separate notion of strict NP-hardness.

8:51 TSP Is Strongly NP-Hard via Hamiltonian Cycle

Reduce undirected Hamiltonian Cycle to TSP by assigning distance 1 to graph edges and distance 2 to non-edges.
Set the TSP tour-length threshold to n, the number of cities: a tour of length n uses only original graph edges and therefore gives a Hamiltonian cycle.
All constructed distances are at most 2, so the reduction proves TSP remains NP-hard even when its numeric values are bounded by a small linear limit.
The class discussion also raises Vertex Cover and Bin Packing as examples to reason about, leaving Bin Packing's classification for later.

17:09 Unary Encoding Gives an Equivalent Test for Strong NP-Hardness

Strong NP-hardness is equivalent to NP-hardness when the problem's integer values are encoded in unary, where a number such as 1,000 takes about 1,000 marks to write.
If the maximum integer is polynomially bounded, converting values to unary increases input size by only a polynomial factor, preserving NP-hardness.
Conversely, unary input length bounds each represented integer by the input size, so NP-hardness of the unary version directly gives a polynomially bounded hard restriction.
Subdividing an edge of weight 5 into a path of five unit edges illustrates how unary weights can be represented structurally in a graph.

22:36 Knapsack in Unary and the Limits of Pseudo-Polynomial Algorithms

Knapsack's pseudo-polynomial dynamic program becomes polynomial-time when its numbers are encoded in unary, placing the optimization problem in PO.
Pseudo-polynomial dynamic programming can be effective when numeric values are small, but it applies to only a limited set of problems.
Wild notes polynomial factoring as a less typical example with a pseudo-polynomial algorithm dependent on total degree, then closes by contrasting such algorithms with strong-hardness lower bounds.

Transcript excerpt

0:01 We've seen some problems where we could find pseudo polynomial time algorithms, but also there's many many other problems where nobody has succeeded. So, we want to complement this nice algorithmic design technique with a lower bound an impossibility technique. And that's called strong NP-hardness. I think I apologize for the name even though it's not mine, of course. Uh in light of the later theory, you'll see that this is a bit of a a bold name for a It just predates some of the other developments, and so people coined the term when there was a lot of terms available. Maybe um in hindsight is is not great. Uh maybe what we would want to say is is even

0:47 uh hard for small numbers or something like that that conveys a bit more the message. Uh let's start with the definition straight away. From what you've seen, maybe you can guess. We should somehow express that the problem remains hard even if the numbers are are small. Because then a pseudo polynomial time algorithm uh can't exist, right? This is the intuition, I think, is clear if um if an algorithm is only exponential in the size of in the value of these numbers, and the problem is hard even with small numbers, well, then probably you don't have such an algorithm. Formally, um and note that I've I've um I've renamed the variables. It's kind of if you want

1:35 to check, I've updated this consistently retroactively in in unit two, as well. I want to be a bit more strict about talking about problems, which are always denoted by pi for problem. Um versus just the language for decision problems was a bit in clash with the optimization version. So, L was used for two two different

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).