Restriction (Decision Problem)

Definition

Restriction (Decision Problem)

Let $\Pi =⟨D,Y⟩$ be a decision problem, where $D$ is its instance set and $Y$ its set of yes-instance. For $R\subseteq D$, the restriction of $\Pi$ to $R$ is

$$\Pi {|}_R:=⟨R,Y\cap R⟩.$$

Only instances in $R$ are allowed; the yes/no question stays unchanged. An instance outside $R$ is excluded, not turned into a no-instance.

Example

Bounding the numbers

Let $b(I)$ be the binary encoding length of $I$, and let $M(I)$ be its largest numerical magnitude. For a fixed polynomial $q$, define

$$R_q:=\{I\in D:M(I)\le q(b(I))\},{\Pi }_q:=\Pi {|}_{R_q}.$$

The problem ${\Pi }_q$ 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 $q$.

Subset sum with small weights

Restrict subset sum to positive integer weights $w_1,\dots ,w_n\le n$. The question remains: does some subset sum to the target $W$?

Since ${\sum }_i{w}_i\le n^2$, reject immediately if $W>n^2$; otherwise the $O(nW)$ dynamic programme takes $O(n^3)$ time. This restriction is easier than unrestricted subset sum.