Verificando uma sutileza da prova original de Karp de que o SAT tem uma redução de tempo polinomial para 3SAT

Em poucas palavras, minha pergunta é: a prova original de Karp está reduzindo o SAT para 3SAT desnecessariamente elaborado? Os detalhes são os seguintes.

Em seu artigo de 1972, Redutibilidade entre problemas combinatórios , Karp provou que o SAT se reduz a 3SAT, afirmando:

Substituir um cláusula , onde o são literais e , por $\sigma_1 \cup \sigma_2 \cup \ldots \cup \sigma_m$ $\sigma_i$ $m>3$ que é uma nova variável. Repita essa transformação até que nenhuma cláusula tenha mais de três literais.
$(σ_{1} \cup σ_{2} \cup u_{1}) (σ_{3} \cup \dots \cup σ_{m} \cup {\bar{u}}_{1}) ({\bar{σ}}_{3} \cup u_{1}) \dots ({\bar{σ}}_{m} \cup u_{1}),$ $(\sigma_1 \cup \sigma_2 \cup u_1) (\sigma_3 \cup \ldots \cup \sigma_m \cup \bar{u}_1) (\bar{\sigma}_3 \cup u_1) \ldots (\bar{\sigma}_m \cup u_1),$ $u_1$

Parece-me que as cláusulas finais (ou seja, as cláusulas que contêm dois literais) aqui são desnecessárias. Portanto, a construção está correta como está escrita, mas é mais elaborada do que o necessário. Sem as cláusulas 2-literais, obtemos a construção geralmente dada nos livros didáticos de graduação. Isso está correto ou estou faltando algo óbvio? Sinto-me extremamente inseguro, sugerindo que qualquer coisa feita por Karp possa ser expressa de maneira mais elegante. $m-2$

cc.complexity-theory sat reductions John MacCormick
fonte

Respostas:

$(\sigma_1\cup\sigma_2\cup u_1)(\sigma_3\cup\ldots\cup\sigma_m\cup\bar{u}_1)$ $\sigma_i$ $u_1$ $\sigma_i$ $u_1$ $\bar{u}_1$

$u_1$ $\sigma_3\cup\ldots\cup\sigma_m$

Klaus Draeger
fonte

Obrigado pela resposta útil. Reformulando para ampliar e verificar meu entendimento, outra maneira de afirmar isso é que as cláusulas extras garantem que essa é uma redução de #SAT para # 3SAT (uma vez que preservam o número de soluções e não apenas a existência de soluções).

precisa