Definition
Restriction (Decision Problem)
Let
be a decision problem, where is its instance set and its set of yes-instance. For , the restriction of to is Only instances in
are allowed; the yes/no question stays unchanged. An instance outside is excluded, not turned into a no-instance.
Example
Bounding the numbers
Let
be the binary encoding length of , and let be its largest numerical magnitude. For a fixed polynomial , define The problem
asks the original question, but only on inputs whose numbers satisfy the bound. Strong NP-hardness means that this restricted problem remains NP-hard for some polynomial .
Subset sum with small weights
Restrict subset sum to positive integer weights
. The question remains: does some subset sum to the target ? Since
, reject immediately if ; otherwise the dynamic programme takes time. This restriction is easier than unrestricted subset sum.