b"\n_START_ARTICLE_\nTeorema da Dicotomia de Schaefer\n_START_PARAGRAPH_\nEm teoria da complexidade computacional, um ramo da Ci\xc3\xaancia da Computa\xc3\xa7\xc3\xa3o, o\xc2\xa0teorema da dicotomia de Schaefer\xc2\xa0estabelece as condi\xc3\xa7\xc3\xb5es necess\xc3\xa1rias e suficientes sob as quais um conjunto finito\xc2\xa0S\xc2\xa0de rela\xc3\xa7\xc3\xb5es sobre o dom\xc3\xadnio Booleano produza problemas de tempo polinomial ouNP-completo quando as rela\xc3\xa7\xc3\xb5es de\xc2\xa0\xc2\xa0S s\xc3\xa3o usadas para restringir algumas das vari\xc3\xa1veis proposicionais.\xc2\xa0_NEWLINE_\xc3\x89 chamado de\xc2\xa0teorema da dicotomia\xc2\xa0porque a complexidade do problema definido por S\xc2\xa0ser\xc3\xa1 P ou NP-completo em oposi\xc3\xa7\xc3\xa3o a alguma das classes de complexidade NP-Intermedi\xc3\xa1rio que \xc3\xa9 sabida existir (assumindo P \xe2\x89\xa0 NP) pelo teorema de Ladner._NEWLINE_Casos especias do teorema da dicotomia de Schaefer incluem a NP-completude de SAT (o problema da satisfatibilidade Booleana) e suas duas variantes populares 1-in-3 SAT\xc2\xa0e NAE-3SAT (Not-All-Equal 3SAT). Na verdade, para estas duas variantes de SAT, o teorema da dicotomia de Schaefer nos mostra suas vers\xc3\xb5es mon\xc3\xb3tonas (onde as nega\xc3\xa7\xc3\xb5es das vari\xc3\xa1veis n\xc3\xa3o s\xc3\xa3o permitidas) tamb\xc3\xa9m s\xc3\xa3o NP-completas.\n_START_SECTION_\nPropriedades do Polimorfismo\n_START_PARAGRAPH_\nDado um conjunto \xce\x93 de rela\xc3\xa7\xc3\xb5es, h\xc3\xa1 uma conex\xc3\xa3o surpreendentemente pr\xc3\xb3xima entre seus polimorfismos e a complexidade computacional de CSP(\xce\x93)._NEWLINE_Uma rela\xc3\xa7\xc3\xa3o R\xc2\xa0 \xc3\xa9 chamada de primitiva positiva defin\xc3\xadvel, ou\xc2\xa0pp-defin\xc3\xadvel, de um conjunto \xce\x93 de rela\xc3\xa7\xc3\xb5es se\xc2\xa0R(v\xe2\x82\x81, ... , v\xe2\x82\x96) \xe2\x87\x94 \xe2\x88\x83x\xe2\x82\x81 ... x\xe2\x82\x98. C\xc2\xa0possui de alguma conjun\xc3\xa7\xc3\xa3o de\xc2\xa0C\xc2\xa0de restri\xc3\xa7\xc3\xb5es de \xce\x93 e equa\xc3\xa7\xc3\xb5es sobre as vari\xc3\xa1veis\xc2\xa0\xc2\xa0{v\xe2\x82\x81,...,v\xe2\x82\x96, x\xe2\x82\x81,...,x\xe2\x82\x98}. Por exemplo, se \xce\x93 consiste da rela\xc3\xa7\xc3\xa3o tern\xc3\xa1ria\xc2\xa0nae(x,y,z) tendo que se x,y,z n\xc3\xa3o s\xc3\xa3o iguais, e R(x,y,z) \xc3\xa9\xc2\xa0x\xe2\x88\xa8y\xe2\x88\xa8z, ent\xc3\xa3o\xc2\xa0R pode ser pp-definida por\xc2\xa0R(x,y,z) \xe2\x87\x94 \xe2\x88\x83a. nae(0,x,a) \xe2\x88\xa7 nae(y,z,\xc2\xaca); testa mesma redu\xc3\xa7\xc3\xa3o foi usada para provar que o problema NAE-3SAT \xc3\xa9 NP-completo. O conjunto de todas as rela\xc3\xa7\xc3\xb5es que s\xc3\xa3o pp-defin\xc3\xadveis de \xce\x93 \xc3\xa9 denotado por\xc2\xa0\xe2\x89\xaa\xce\x93\xe2\x89\xab. Se \xce\x93' \xe2\x8a\x86 \xe2\x89\xaa\xce\x93\xe2\x89\xab para quaisquer conjuntos finitos limitados \xce\x93 e\xce\x93', ent\xc3\xa3o CSP(\xce\x93') \xc3\xa9 redut\xc3\xadvel \xc3\xa0\xc2\xa0CSP(\xce\x93)._NEWLINE_Dado um conjunto \xce\x93 de rela\xc3\xa7\xc3\xb5es,\xc2\xa0Pol(\xce\x93) denota o conjunto de polimorfismos de \xce\x93. Se\xc2\xa0O\xc2\xa0\xc3\xa9 um conjunto de opera\xc3\xa7\xc3\xb5es, ent\xc3\xa3o\xc2\xa0Inv(O)\xc2\xa0denota o conjunto de rela\xc3\xa7\xc3\xb5es tendo todas as suas opera\xc3\xa7\xc3\xb5es em O como polimorfismo.\xc2\xa0Pol e\xc2\xa0Inv\xc2\xa0juntos constroem uma conex\xc3\xa3o de\xc2\xa0Galois. Para qualquer conjunto finito \xce\x93 de rela\xc3\xa7\xc3\xb5es sobre um dom\xc3\xadnio finito, \xe2\x89\xaa\xce\x93\xe2\x89\xab = Inv(Pol(\xce\x93)) cont\xc3\xa9m, isto \xc3\xa9, o conjunto de rela\xc3\xa7\xc3\xb5es pp-defin\xc3\xadveis de \xce\x93 que podem ser derivadas dos polimorfismos de \xce\x93. Se\xc2\xa0Pol(\xce\x93) \xe2\x8a\x86 Pol(\xce\x93') para dois conjuntos finitos de rela\xc3\xa7\xc3\xb5es \xce\x93 e \xce\x93', ent\xc3\xa3o \xce\x93' \xe2\x8a\x86 \xe2\x89\xaa\xce\x93\xe2\x89\xab and CSP(\xce\x93')\xc2\xa0reduzem \xc3\xa0 CSP(\xce\x93). Por consequ\xc3\xaancia, dois conjuntos de rela\xc3\xa7\xc3\xb5es possuindo os mesmos polimorfismos levam \xc3\xa0 mesma complexidade computacional.\n_START_SECTION_\nGeneraliza\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nA an\xc3\xa1lise foi posteriormente refinada: CSP(\xce\x93) ser\xc3\xa1 resolv\xc3\xadvel em tempo co-NLOG, L-completo, NL-completo, \xe2\x8a\x95L-completo, P-completo\xc2\xa0ou\xc2\xa0NP-completo\xc2\xa0e dado \xce\x93, \xc3\xa9 poss\xc3\xadvel decidir em tempo polinomial qual destes casos \xc3\xa9 correspondente._NEWLINE_O teorema da dicotomia de Schaefer foi recentemente generalizado para uma classe maior de rela\xc3\xa7\xc3\xb5es.\n_START_SECTION_\nTrabalhos Relacionados\n_START_PARAGRAPH_\nCaso o problema seja o de contar o n\xc3\xbamero de solu\xc3\xa7\xc3\xb5es, denotado por #CSP(\xce\x93), ent\xc3\xa3o um resuldado similar criado por Creignou e Hermann efetiva.Seja \xce\x93 uma linguagem finita restringida sobre o dom\xc3\xadnio Booleano. O problema #CSP(\xce\x93) \xc3\xa9 comput\xc3\xa1vel em tempo polinomial se \xce\x93 possuir uma opera\xc3\xa7\xc3\xa3o Mal'tsev como polimorfismo. Do contr\xc3\xa1rio, o problema #CSP(\xce\x93) \xc3\xa9 #P-completo.\xc2\xa0Uma opera\xc3\xa7\xc3\xa3o Mal'tsev ''m''\xc3\xa9 uma opera\xc3\xa7\xc3\xa3o tern\xc3\xa1ria que satisfaz\xc2\xa0\xc2\xa0Um exemplo de uma opera\xc3\xa7\xc3\xa3o Mal'tsev \xc3\xa9 a opera\xc3\xa7\xc3\xa3o de Minoria dada na formula\xc3\xa7\xc3\xa3o moderna do teorema da dicotomia de Schaefer atrav\xc3\xa9s da \xc3\xa1lgebra universal na sess\xc3\xa3o acima. Portanto, quando \xce\x93 possuir a opera\xc3\xa7\xc3\xa3o Minoria como um polimorfismo, \xc3\xa9 n\xc3\xa3o somente poss\xc3\xadvel decidir CSP(\xce\x93) em tempo polinomial, mas tamb\xc3\xa9m computar #CSP(\xce\x93) em tempo polinomial. Outros exemplos de opera\xc3\xa7\xc3\xb5es Mal'tsev incluem\xc2\xa0 and _NEWLINE_Para dom\xc3\xadnios maiores, mesmo para um dom\xc3\xadnio de tamanho tr\xc3\xaas, a exist\xc3\xaancia de um Maltsev como polimorfismo de \xce\x93 n\xc3\xa3o mais \xc3\xa9 condi\xc3\xa7\xc3\xa3o suficiente para a tratabilidade de #CSP(\xce\x93). No entanto, a absc\xc3\xaancia de um polimorfismo Mal'tsev para este \xce\x93 ainda implica a #P-dificuldade de #CSP(\xce\x93)."