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 Teorema da dicotomia de Schaefer declara condi\xc3\xa7\xc3\xb5es necess\xc3\xa1rias e suficientes sob as quais um conjunto finito S de rela\xc3\xa7\xc3\xb5es sobre o dom\xc3\xadnio Booleano gera problemas de tempo polinomial ou problemas NP-completos quando as rela\xc3\xa7\xc3\xb5es de S s\xc3\xa3o usadas para restringir algumas das vari\xc3\xa1veis proposicionais.  \xc3\x89 chamado teorema da dicotomia porque a complexidade do problema definido por S ou est\xc3\xa1 em P ou NP-complete, ao contr\xc3\xa1rio das classes de complexidade intermedi\xc3\xa1ria que sabemos que existem (assumindo P \xe2\x89\xa0 NP) de acordo com o teorema de Ladner._NEWLINE_Casos especiais do teorema da dicotomia de Schaefer incluem a NP-completude de SAT (o Problema de satisfatibilidade booleana) e suas duas variantes populares SAT 1-em-3 e 3SAT Nem-Todos-Iguais (comumente chamado 3SAT-NTI). De fato, para essas duas variantes de SAT, o teorema da dicotomia de Schaefer mostra que suas vers\xc3\xb5es mon\xc3\xb3tonas(onde nega\xc3\xa7\xc3\xb5es de vari\xc3\xa1veis n\xc3\xa3o s\xc3\xa3o permitidas) tamb\xc3\xa9m s\xc3\xa3o NP-completas.\n_START_SECTION_\nGeneraliza\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nA an\xc3\xa1lise foi mais tarde aperfei\xc3\xa7oada: CSP(\xce\x93) ou \xc3\xa9 sol\xc3\xbavel em co-NLOGTIME, L-completo, NL-completo, \xe2\x8a\x95L-completo, P-completo ou NP-completo e dado \xce\x93, pode-se decidir em tempo polinomial qual desses casos acontece._NEWLINE_O teorema da dicotomia de Schaefer foi recentemente generalizado como sendo uma classe maior de rela\xc3\xa7\xc3\xb5es.\n_START_SECTION_\nMaterial relacionado\n_START_PARAGRAPH_\nSe o problema \xc3\xa9 contar o n\xc3\xbamero de solu\xc3\xa7\xc3\xb5es, o qual \xc3\xa9 denotado por #CSP(\xce\x93), ent\xc3\xa3o um resultado similar por Bulatov e Dalmau serve._NEWLINE_Seja \xce\x93 uma linguagem de restri\xc3\xa7\xc3\xb5es finita sobre o dom\xc3\xadnio dom\xc3\xadnio Booleano. O problema #CSP(\xce\x93) \xc3\xa9 comput\xc3\xa1vel em tempo polinomial se \xce\x93 tem uma opera\xc3\xa7\xc3\xa3o de Mal'tsev como um polimorfismo. Caso contr\xc3\xa1rio, o problema #CSP(\xce\x93) \xc3\xa9 #P-completo._NEWLINE_Uma opera\xc3\xa7\xc3\xa3o de Mal'tsev m \xc3\xa9 uma opera\xc3\xa7\xc3\xa3o tern\xc3\xa1ria que satisfaz  Um exemplo de opera\xc3\xa7\xc3\xa3o de Mal'tsev \xc3\xa9 a opera\xc3\xa7\xc3\xa3o de Minoria dada na formula\xc3\xa7\xc3\xa3o moderna, alg\xc3\xa9brica do Teorema da dicotomia de Schaefer acima. Portanto, quando \xce\x93 tem a opera\xc3\xa7\xc3\xa3o de Minoria como um polimorfismo, n\xc3\xa3o \xc3\xa9 somente poss\xc3\xadvel decidir CSP(\xce\x93) em tempo polinomial, como tamb\xc3\xa9m computar #CSP(\xce\x93) em tempo polinomial. Outros exemplos de opera\xc3\xa7\xc3\xb5es de Mal'tsev incluem  e _NEWLINE_Para dom\xc3\xadnios maiores, mesmo um dom\xc3\xadnio de tamanho tr\xc3\xaas, a exist\xc3\xaancia do polimorfismo de Mal'tsev polymorphism para \xce\x93 n\xc3\xa3o \xc3\xa9 mais uma condi\xc3\xa7\xc3\xa3o suficiente para a tratabilidade de #CSP(\xce\x93). Entretando, a aus\xc3\xaancia do polimorfismo de Mal'tsev para \xce\x93 ainda implica na #P-dificuldade de #CSP(\xce\x93)."