Por que o teorema de Schaefer não prova que P = NP?

12

Esta é provavelmente uma pergunta estúpida, mas eu simplesmente não entendo. Em outra questão, eles apresentaram o teorema da dicotomia de Schaefer . Para mim, parece que prova que todo problema de CSP está em P ou em NP-complete, mas não no meio. Como todo problema de NP pode ser transformado no tempo polinomial em CSP (porque o CSP é NP-completo), por que isso não prova que não há espaço entre P e NP-Completo e, portanto, P = NP?

Por exemplo, na minha opinião, a fatoração inteira pode ser reescrita como um problema de satisfação; portanto, usando o teorema de Schaefer, ele deve estar em P ou NP-completo, mas não no meio (mesmo que não possamos descobrir qual é).

Uma maneira diferente de analisar toda a questão: Por que não podemos usar o teorema de Schaefer para decidir se a fatoração inteira está em P ou em NP-completo?


EDIT: em resposta à resposta de David Richerby (é muito longo para um comentário):

Interessante, mas ainda não entendo completamente. Ao definir o conjunto de relações gama enquanto usamos o teorema de Schaefer, podemos impor restrições a ele. Por exemplo, podemos restringir a gama a usar apenas relações da aridade 2 (o problema está em P). Que tipo de restrições podemos impor à gama?

Por que não podemos impor tais restrições que todas as instâncias de CSP (gama) são exatamente as mesmas que (isomórficas para?) L? Por exemplo, ao transacionar a fatoração inteira para números desiguais, um dos dois divisores é binário representado como xn .. x3 x2 1. Agora, quero que esse número seja maior que 1. Portanto, tenho a relação (xn ou .. ou x3 ou x2). Então, eu digo que gama pode ter uma relação de aridade n-1. Mas eu não quero que essa relação-ou seja usada para incluir outras instâncias além de L na linguagem, além disso, imponho que x2..xn na relação-ou não tenha negação. Claro, eu também preciso impor a restrição de que apenas variáveis ​​específicas sejam usadas lá.

Não é possível, dessa maneira, permitir que o CSP (gama) seja isomórfico à fatoração de número inteiro? A principal questão é: que tipo de restrições podemos impor à gama?

EDIT 2: em resposta à resposta de Yuval Filmus.

Entendo sua resposta e ela parece correta, embora aproximadamente a mesma que a resposta de Davi. Por exemplo, podemos reduzir a fatoração para 3-sat e, em seguida, concluir que a fatoração está NP completa, o que está errado porque o 3-sat possui outras instâncias que provavelmente não são fatoração.

A parte que eu não entendo é quando uma instância é (não) arbitrária. Por exemplo, o 2-SAT também me parece não arbitrário, porque apenas são permitidas cláusulas da aridade 2 (embora eu deva admitir que a prova ainda é válida porque é um limite superior e, nesse caso, o limite superior é P).

Talvez um exemplo melhor seja o de NP-completeness: a questão vinculada acima. Um respondente dá uma prova completa de Schaefer. Mas eu imponho restrições não triviais à entrada (cláusulas 2-SAT são permitidas e cláusulas xor, mas nada mais). Obviamente, a prova ainda é válida porque os problemas de CSP considerados na prova são exatamente os mesmos que o original.

A parte que eu não entendo é por que não podemos fazer o mesmo para fatoração? É claro que não adianta reduzi-lo para 3-SAT, mas permita-me fornecer a instância do CSP que fatora um número e somente um número (de 4 bits). (pule para END-OF-SKIP se achar que isso é possível).

Instância de fatoração.

ENTRADA:

(N =) (os 4 bits do número a ser fatorado) (M =) m 4 m 3 m 2 m 1 (os 4 bits do valor mínimo do primeiro divisor) n4n3n2n1
m4m3m2m1

Agora, vamos transformar isso em uma instância do CSP

ENTRADA:
domínios unários para e para m 5 . . m 1 (representando que N e M são dados)n5..n1m5..m1

variáveis ​​com domínio {0,1}:
(D =) (o primeiro divisor) (E =) e 4 e 3 e 2 e 1 (o segundo divisor)d4d3d2d1
e4e3e2e1

relações:

(representando E> 1)e4e3e2

(que representa D> H)(d4¬m4)(d4=m4d3¬m3)(d4=m4d3=m3d2¬m2)(d4=m4d3=m3d2=m2d1¬m1)

(representando multiplicação bit menos significativo), ( d 1e 2 ) ( d 2e 1 ) = n 2 (representando a multiplicação de bits seguinte) n 3 = . . . ; n 4 = . . .d1e1=n1
(d1e2)(d2e1)=n2
n3=...;n4=...

FIM DE SALTO

O ponto crucial é que, ao aplicar o teorema de Schaefer, devemos considerar apenas esses CSPs . (Assim como no 2-SAT, consideramos apenas CSPs com arity 2). Ao fazer isso, um dos seis polimorfismos se mantém ou não (exceto algumas peculiaridades na teoria dos conjuntos). Em ambos os casos, a fatoração não é NP intermediária.

Isso também pode ser feito para o 3-SAT. Então, devemos considerar apenas (usando a redução) instâncias 3-SAT que representam instâncias de fatoração (que não são mais 3-SAT).

Onde eu errei?

Albert Hendriks
fonte
1
Eu sugiro fortemente que você leia uma formulação exata do teorema da dicotomia de Schaefer. Não é verdade que você "possa impor restrições ao [conjunto de relações]". O teorema da dicotomia de Schaefer não cobre este caso. Às vezes, a Wikipedia pode ser imprecisa e confusa, por isso sugiro que você encontre notas de aula ou talvez veja um artigo relevante.
Yuval Filmus
Não notei seu comentário antes de editar minha resposta. Talvez não seja permitido impor restrições ao conjunto de relações, mas parece-me que você não deve considerar relações que não correspondem à restrição ao aplicar o teorema de Schaefer. Assim como no 2-SAT, você não considera relações que não correspondem à "restrição" de que cada cláusula deve ter 2 literais.
Albert Hendriks
2
ΓCSP(Γ)ΓCSP(Γ)
3
CSP(Γ)
1
Alguém conhece um bom livro ou um tratamento moderno da dicotomia Schaeffer?
vzn

Respostas:

10

LΓΓLLΓLΓ

David Richerby
fonte
Interessante. Eu editei minha pergunta em resposta à sua resposta.
Albert Hendriks
ΓΓΓ
Posso estar errado, mas eu diria que a entrada para o problema de fatoração Inteiro é a mesma que a entrada para CSP (gama): quaisquer dois números binários (o número a ser fatorado e o valor mínimo de um dos divisores) . Certo? Entendo a parte de que, se você não fizer a transformação com cuidado, terá um outro problema.
Albert Hendriks
ΓΓ
12

ΓCSP(Γ)

ΓCSP(Γ)

Yuval Filmus
fonte
Obrigado pela sua resposta. Editei minha pergunta (EDIT 2) em resposta à sua resposta.
Albert Hendriks