Considere o problema 3-SAT em n variáveis. O número de possíveis cláusulas distintas é:
O número de casos de problemas é o número de todos os subconjuntos do conjunto de possíveis cláusulas: . Trivialmente, para cada , existe pelo menos uma instância satisfatória e uma instância insatisfatória. É possível calcular, ou pelo menos estimar, o número de instâncias satisfatórias para um dado n?
cc.complexity-theory
sat
Antonio Valério Miceli-Barone
fonte
fonte
Respostas:
Uma longa história de trabalho em transições de fase no SAT mostrou que, para qualquer fixo , há um limite parametrizado pela razão do número de cláusulas para que decide a satisfação. Grosso modo, se a proporção for menor que 4,2, com probabilidade esmagadora, a instância é satisfatória (e, portanto, uma fração enorme do número de instâncias com essas muitas cláusulas e variáveis é satisfatória). Se a proporção estiver ligeiramente acima de 4,2, o inverso se mantém - uma fração esmagadora de instâncias é insatisfatória.n n
As referências são demais para citar aqui: uma fonte de informação é o livro de Mezard e Montanari . Se alguém tiver fontes de pesquisas, etc., sobre esse tópico, ele poderá publicá-lo nos comentários ou editar esta resposta.
Referências:
- levantamento Achlioptas
- onde os problemas realmente difíceis são
- Refinando a transição de fase em busca combinatória
fonte
Por um lado, a grande maioria das instâncias será insatisfatória, como dito no comentário de Suresh. (De fato, acho que se você experimentar uma dessas instâncias uniformemente aleatoriamente, já deverá ter uma boa probabilidade de incluir todas as oito negações como cláusulas para alguma variável tripla, ou seja, trivialmente insatisfatória.)2|C|
Por outro lado, podemos limitar o número de instâncias satisfatórias pelo número que é satisfeito pela atribuição zero: elas seriam , como para cada tripleto de variáveis existentes é uma cláusula que não podemos usar.2(7/8)|C|
Pode-se então limitar o número de instâncias satisfatórias multiplicando-o por . Como , acho que isso apenas altera um termo de ordem menor já ...2n |C|=O(n3)
fonte
Essa resposta lida apenas com a taxa de crescimento do número de instâncias satisfatórias.
Um conjunto é escasso se o número de seqüências de n bits no conjunto for delimitado por (para alguma constante ), caso contrário, é denso. Sabe-se que satisfação (NP-completa) e Insatisfação (CoNP-completa) são conjuntos densos. Existem conjuntos incompletos de esparsos, se .O ( n k ) k N P P = N PA O(nk) k NP P=NP
fonte