TL; DR : a redução polinomial aumenta o tamanho de um problema; o uso de um solucionador específico permite explorar a estrutura de um problema.
Quando você reduz um problema de NP-completo para outro, o tamanho do problema geralmente aumenta polinomialmente. Por exemplo, quando você reduz um HAMPATH em um gráfico comn nós para SAT, a fórmula resultante tem tamanho de Θ(n3)(Não me lembro da constante que surge em uma redução direta de TSP-> SAT). Se você usar o teorema de Cook-Levin, o crescimento poderá ser ainda maior porque uma máquina de Turing pode ter uma sobrecarga (polinomial) realmente enorme. NP-completude é principalmente uma idéia teórica. O mesmo ocorre com uma redução no tempo polinomial. Muitos trabalhos teóricos afirmam apenas que há uma redução, sem dizer nada sobre o quão prático é.
Vamos assumir informalmente que o TSP é tão difícil quanto o SAT. Isso significa que são necessários recursos computacionais semelhantes para resolver o TSP emn nós e SAT com ncláusulas se você usar solucionadores de ponta para cada problema. Agora é fácil ver que escrever um solucionador separado é mais prático do que reduzir o problema ao SAT e usar algum solucionador existente. É tudo sobre sobrecarga polinomial.
Há mais uma coisa a se notar: os problemas exatos são geralmente mais simples que os amplos. Quando você reduz o TSP para o SAT, o solucionador SAT não sabe nada sobre a estrutura subjacente da fórmula. E solucionadores especiais para TSP, é claro, lidam com o fato de que a entrada é um gráfico, o problema é encontrar um caminho hamiltoniano mais curto, etc.
Embora, para alguns problemas, a redução do SAT possa ser razoável, principalmente se o problema não for bem estudado (e não houver solucionadores interessantes) e quando a redução não aumentar muito o tamanho do problema. Os solucionadores de SAT ainda são muito fortes para muitos propósitos práticos.
