Teorema de Schaefer e CSPs de largura ilimitada

O teorema da dicotomia de Schaefer mostra que cada problema de CSP acima de é solucionável em tempo polinomial ou é NP completo. Isso se aplica apenas a problemas CSP de largura limitada, excluindo SAT e Horn-SAT, por exemplo. Os problemas gerais de largura ilimitada do CSP podem ser muito difíceis (até mesmo incontestáveis); portanto, vamos nos restringir a problemas que são "naturais" e estão no NP.$\{0,1\}$

Dado um problema CSP de largura ilimitada, para cada , podemos observar a restrição do problema para cláusulas de largura até k . O teorema de Schaefer agora se aplica, e o problema restrito está em P ou NP-completo. Se, para alguns k , o problema restrito a k é NP-completo, o mesmo ocorre com o problema irrestrito. A situação é menos clara quando, para todos os k , o problema restrito a k está em P.$k$$k$$k$$k$$k$$k$

O teorema da dicotomia de Schaefer se baseia em quatro (aproximadamente) algoritmos diferentes que resolvem todos os casos fáceis. Suponha que, para um determinado problema de CSP, o problema com restrição de seja sempre solucionável pelo algoritmo A. Pode ser que o algoritmo A também possa ser usado para resolver o problema sem restrição. Ou pode ser que o algoritmo A não seja um tempo polinomial no caso irrestrito, e então ignoramos a dureza do problema.$k$

Esse tipo de problema foi considerado? Existem exemplos em que chegamos ao ponto "ignorante"?

Eu afirmo que, para um "CSP booleano natural", se a versão restrita a k estiver em P para cada k , a versão irrestrita também estará em P. Definirei um "CSP booleano natural" abaixo.

O teorema de Schaefer afirma que o CSP booleano em um conjunto finito S de relações está em P se pelo menos uma das seguintes condições for satisfeita e é NP completo se nenhuma delas for satisfeita:

1. Toda relação em S (exceto a constante 0) é satisfeita atribuindo 1 a todas as suas variáveis.
2. Toda relação em S (exceto a constante 0) é satisfeita atribuindo 0 a todas as suas variáveis.
3. Toda relação em S é equivalente a uma fórmula 2-CNF.
4. Toda relação em S é equivalente a uma fórmula da cláusula de Horn.
5. Toda relação em S é equivalente a uma fórmula de cláusula de chifre duplo. (Uma "fórmula de cláusula de chifre duplo" significa uma fórmula de CNF em que cada cláusula contém no máximo um literal positivo.)
6. Toda relação em S é equivalente a uma conjunção de cláusulas afins.

Agora assuma que P ≠ NP e considere o caso em que S é infinito. Se a versão com restrição k está em P para cada k , pelo teorema de Schaefer, todo subconjunto finito de S satisfaz pelo menos uma das seis condições acima, e isso significa que todo o conjunto S satisfaz pelo menos uma das seis condições. Isso significa que esse CSP sem a restrição de aridade também está em P? Ainda não.

Quando S é infinito, temos que especificar como cada cláusula na fórmula de entrada é fornecida. Assumimos que há algum mapeamento surjective entre {0,1} ^* para S , que especifica a codificação das relações em S . Um CSP booleano é especificado, fornecendo S e essa função de codificação.

Observe que em cada um dos casos 3, 4, 5 e 6 acima, existe uma maneira natural de representar relações que satisfazem a condição: uma fórmula 2-CNF no caso 3, uma fórmula de cláusula de Horn no caso 4 e assim por diante. Mesmo que uma relação seja equivalente a (digamos) uma fórmula 2-CNF, não há garantia a priori de que sua codificação fornece um acesso fácil à fórmula 2-CNF que é equivalente a ela.

Agora dizemos que um CSP booleano é natural quando sua função de codificação satisfaz o seguinte:

• Dada uma codificação de uma relação e uma atribuição a todas as suas variáveis, se a relação é satisfeita ou não, pode ser calculada em tempo polinomial. (Nota: Isso garante que o CSP em questão esteja sempre no NP.)
• Dada a codificação de uma relação que satisfaça as condições 3, 4, 5 ou 6, sua representação natural, conforme especificado acima, pode ser calculada em tempo polinomial.

É fácil ver que, se S satisfaz uma das seis condições acima e a codificação para S satisfaz essa condição de "naturalidade", podemos aplicar o algoritmo correspondente. A alegação que afirmei no início pode ser comprovada considerando-se tanto o caso de P = NP quanto o caso de P ≠ NP.