7
$\begingroup$

Often I see a sentence like this while reading texts on Computational Complexity:

"For this special case of $\text{TSP}$" or

"This is a special case of $\text{SAT}$" or

"$k$-$\text{PARTITION}$ is the following special case of $\text{BIN PACKING}$" or

"$\text{SUBSET SUM}$ is a special case of $\text{KNAPSACK}$" ad nauseam.

What I find missing is the criterium to claim one problem is a special case of another.
What is the necessity of classifying one problem as a special case of another? Does a special case always carry the complexity class as its 'unspecial' case?

Often this is simply stated with no proof of relation between these problems.

What requirements must be met for a problem to be a special case of another?

How can I prove a new Language for a problem is a special case of an already existing problem?

$\endgroup$
11
$\begingroup$

When we say that a problem $B$ is a special case of a problem $A$, we mean that $B$ is the same problem as $A$, with the exception that not all problem instances of $A$ are problem instances for $B$. If $B$ is a special case of $A$, we say that $A$ is a generalization of $B$.

Two examples: the addition of positive whole numbers (say $5 + 3$) is a special case of addition of whole numbers (say $5 + (-3)$), and sorting of integers in the range $\{ 1, 2, \dots, k \}$ for fixed $k$ is a special case of sorting of arbitrary integers.

Any solution to $A$ is also a solution to $B$, and any hardness results for $B$ (for example, it is $NP$-hard or needs $\Omega(n^2)$ time to be solved) immediately transfer to $A$. However, we usually consider special cases because we can sometimes find better algorithms for them compared to the general case.

Examples: the $\Theta(n \log n)$ sorting algorithm works just as well on integers in the range $\{ 1, 2, \dots, k \}$, but CountingSort works on the special case (not on the general) in $O(n + k)$, which is usually faster if $k$ is small. $SAT$ is $NP$-hard, $3SAT$ is a special case of $SAT$ that is still $NP$-hard (which therefore implies that $SAT$ is $NP$-hard), but $2SAT$ is in $P$.

Note that the above definition is sometimes stretched (abused) to say that you can encode any instance of $B$ as an instance of $A$, and that this encoding is extremely simple. In that case, the above usually still holds, but is less rigorous.

$\endgroup$
4
$\begingroup$

"Special case" is simply the opposite of "general case".

For instance, a tree is a special case of a graph, etc. The same works for problems: "find the minimal element of some list" or "find the median" are merely special cases of the problem "find the $k$-th smallest element in the list".

As for the complexity, we know that the special case is at most as hard as the general case (because any algorithm that solves the general case, can also solve the special case).

However, it is possible that the special case is way more simple than the general case. Many $\text{NP}$-complete problems have special cases that are "easy" to solve. For instance, 2-$\text{SAT}$ which is the special case of $\text{SAT}$ in which the formula has only 2 variables in each clause. While $\text{SAT}$ is $\text{NP}$-complete, 2-$\text{SAT}$ can be solved with polynomial time.

Another example: although sorting takes $\Omega(n\log n)$ in general, for the special case in which the domain is bounded (i.e., the elements are only from $\{1, \ldots, m\}$ for a fixed $m$), a linear $O(n+m)$ solution exists using Bucket sort, etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.