Complexidade de problemas de casos especiais

Muitas vezes, vejo uma frase como essa ao ler textos sobre Complexidade Computacional:

"Para este caso especial de " ou$\text{TSP}$

"Este é um caso especial de " ou$\text{SAT}$

" - é o seguinte caso especial de " ou$k$$\text{PARTITION}$$\text{BIN PACKING}$

" é um caso especial de " nauseam.$\text{SUBSET SUM}$$\text{KNAPSACK}$

O que acho que falta é o critério para afirmar que um problema é um caso especial de outro.
Qual é a necessidade de classificar um problema como um caso especial de outro? Um caso especial sempre carrega a classe de complexidade como seu caso 'não-especial'?

Muitas vezes, isso é simplesmente afirmado sem prova de relação entre esses problemas.

Quais requisitos devem ser atendidos para que um problema seja um caso especial de outro?

Como posso provar que um novo idioma para um problema é um caso especial de um problema já existente?

Quando dizemos que um problema $B$ é um caso especial de um problema $A$, queremos dizer que $B$ é o mesmo problema que $A$, com a exceção de que nem todas as instâncias de problemas de $A$ são instâncias de problemas para $B$. E se$B$ é um caso especial de $A$dizemos que $A$ é uma generalização de $B$.

Dois exemplos: a adição de números inteiros positivos (digamos $5 + 3$) é um caso especial de adição de números inteiros (por exemplo, $5 + (-3)$) e classificação de números inteiros no intervalo $\{ 1, 2, \dots, k \}$ para fixo $k$ é um caso especial de classificação de números inteiros arbitrários.

Qualquer solução para $A$ também é uma solução para $B$, e quaisquer resultados de dureza para $B$ (por exemplo, é $NP$-hard ou necessidades $\Omega(n^2)$ tempo a ser resolvido) transfira imediatamente para $A$. No entanto, geralmente consideramos casos especiais porque, às vezes, podemos encontrar algoritmos melhores para eles em comparação com o caso geral.

Exemplos: o $\Theta(n \log n)$ algoritmo de classificação funciona tão bem em números inteiros no intervalo $\{ 1, 2, \dots, k \}$, mas o CountingSort trabalha no caso especial (não no geral) em $O(n + k)$, que geralmente é mais rápido se $k$ é pequeno. $SAT$ é $NP$-Difícil, $3SAT$ é um caso especial de $SAT$ isso ainda é $NP$-hard (o que implica, portanto, que $SAT$ é $NP$-hard), mas $2SAT$ é em $P$.

Observe que às vezes a definição acima é esticada (abusada) para dizer que você pode codificar qualquer instância de $B$ como uma instância de $A$, e que essa codificação é extremamente simples. Nesse caso, o acima geralmente ainda é válido, mas é menos rigoroso.

"Caso especial" é simplesmente o oposto de "caso geral".

Por exemplo, uma árvore é um caso especial de gráfico, etc. O mesmo funciona para problemas : "encontre o elemento mínimo de alguma lista" ou "encontre a mediana" são apenas casos especiais do problema "encontre o$k$-o menor elemento da lista ".

Quanto à complexidade, sabemos que o caso especial é no máximo tão difícil quanto o caso geral (porque qualquer algoritmo que resolva o caso geral também pode resolver o caso especial).

No entanto, é possível que o caso especial seja muito mais simples que o caso geral. Muitos$\text{NP}$problemas incompletos têm casos especiais que são "fáceis" de resolver. Por exemplo, 2$\text{SAT}$ qual é o caso especial de $\text{SAT}$em que a fórmula possui apenas 2 variáveis ​​em cada cláusula. Enquanto$\text{SAT}$ é $\text{NP}$-complete, 2-$\text{SAT}$ pode ser resolvido com tempo polinomial.

Outro exemplo: embora a classificação precise $\Omega(n\log n)$ em geral, para o caso especial em que o domínio é delimitado (ou seja, os elementos são apenas de $\{1, \ldots, m\}$ para um fixo $m$), um linear $O(n+m)$existe uma solução usando a classificação Bucket etc.