Strong NP-Hard Decision Problem

Definition

Strong NP-Hard Decision Problem

Let be a numerical decision problem. For an instance , let be its binary encoding length and its largest numerical magnitude. Define the restriction

The problem is strongly NP-hard if is NP-hard for some fixed polynomial . Thus NP-hardness persists even when all numbers are polynomially bounded in the input length.

For standard numerical problems, this is equivalently expressed as NP-hardness under unary encoding.

Hard in Binary and 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 .

Use the standard explicit binary encoding: zero is written as 0, and every positive integer uses at least one bit. Thus each field has length . This is a convention about the representation, not a restriction on the numerical values. If an alternative encoding allows empty fields, their delimiters must still identify each field; count that space instead. A compressed instruction such as “repeat zero times” is not an explicit list, so this argument does not apply to it.

Distinguish:

• Structural count : since , we have .
• Encoded values : these may be exponentially larger than their bit-lengths.

Strong NP-hardness gives an NP-hard restriction with . Its unary length satisfies

Writing these symbols takes polynomial time and preserves the answer—a Karp reduction:

Thus both encodings remain NP-hard, even with bounded numerical values; neither is polynomial-time solvable unless P = NP.

Why Pseudo-Polynomial Time Is Ruled Out

On the restricted instances, there are at most numerical parameters, each at most . Their unary encoding length therefore satisfies

A pseudo-polynomial time algorithm would then solve the NP-hard restriction in polynomial time. Hence no such algorithm exists unless P = NP, unlike the standard weakly NP-hard examples.

Proving Strong NP-Hardness

Give a polynomial-time reduction whose output numbers are polynomially bounded in the output length. The source may be a known strongly NP-hard problem or a non-numerical problem such as 3-SAT.

Constant-sized output numbers suffice, but are not required: polynomially bounded does not mean constant.

Example

Constant-sized numbers

• The decision version of the travelling salesman problem remains NP-hard with edge weights in .
• The reduction from 3-SAT to vector subset sum uses entries in ; the vector dimension still grows with the instance.

Polynomially bounded numbers

• 3-partition remains NP-hard when its integers are polynomially bounded.
• The decision version of bin packing inherits strong NP-hardness from 3-partition: the item sizes and bin capacity remain polynomially bounded.