Weak NP-Hard Decision Problem

Definition

Weak NP-Hard Decision Problem

A numerical decision problem is weakly NP-hard if it is NP-hard but not strongly NP-hard:

where restricts every numerical magnitude to at most and is the binary encoding length. Here numbers are represented in base two as binary numbers; any other fixed base greater than one gives the same classification.

Pseudo-Polynomial Algorithms

Standard weakly NP-hard problems admit pseudo-polynomial algorithms: their running time is polynomial in the unary encoding length , which may be exponential in .

When every number is at most for a fixed polynomial , there are at most numbers, so

The algorithm therefore runs in polynomial time on every such restriction. Assuming P ≠ NP, this proves that the problem is not strongly NP-hard.

Some texts use “weakly NP-hard” specifically for NP-hard problems with a pseudo-polynomial algorithm. Under the broader definition above, such an algorithm is sufficient, but its existence does not follow merely from the failure of strong NP-hardness.

Hard in Binary, Tractable in Unary

If the unary encoding length is upper-bounded by a fixed polynomial in the binary encoding length , then polynomial time in is also polynomial time in .

Distinguish two kinds of magnitude in an explicitly represented input:

A structural count requires objects to be present in the input. A numerical value need not require symbols:

Changing the number encoding does not change or . It changes how much space occupies: logarithmic in binary, linear in unary.

For a pseudo-polynomial algorithm, a bound therefore gives two different guarantees:

On a restriction with , the numerical magnitude is also polynomially bounded by the binary input length:

Thus, for NP-hard problems with a pseudo-polynomial algorithm:

This conclusion requires a pseudo-polynomial algorithm; “not strongly NP-hard” alone does not guarantee one.

Example

Standard weakly NP-hard problems

• Subset sum admits an dynamic programming algorithm, where is the target.
• The decision version of knapsack admits an algorithm, where is the capacity.
• Partition reduces to subset sum with target half the total weight; an odd total is immediately rejected.

These algorithms are polynomial in the numerical target or capacity, not necessarily in its bit-length.