Informações sobre o k-SAT (introdução, limites, métodos etc.)

9

Gostaria de saber onde posso recorrer para uma introdução boa e gentil ao k-SAT (isso pode ser para matemáticos que podem não ter uma boa formação em ciência da computação). Também gostaria de conhecer trabalhos que talvez pesquisem ou expliquem os métodos atuais usados ​​para resolver o k-SAT. Finalmente, estou interessado nos métodos mais conhecidos para resolver o k-SAT. Gostaria de ter uma idéia do melhor caso médio e do melhor comportamento do pior caso.

Em resumo, estou procurando artigos que ajudarão alguém em matemática (não ciência da computação) a se tornar muito mais especialista em k-SAT.

Matt Groff
fonte
11
Existem boas respostas sobre o k-SAT no site: notas de aula , limites superior e inferior , com muitos links. Tente pesquisar a tag sentou também.
Hsien-Chih Chang,

Respostas:

5

Este livro de pesquisa, Problema de Satisfação: Teoria e Aplicações , é apropriado para a introdução do k-SAT aos matemáticos. Não é um recurso muito recente, mas ainda muito valioso.

Mohammad Al-Turkistany
fonte