Amostragem de fórmulas 3-SAT satisfatórias

23

Considere a seguinte tarefa computacional: Queremos provar uma fórmula 3-SAT de variáveis ​​(uma variante: variáveis cláusulas) com relação à distribuição uniforme de probabilidade, condicionada à satisfação da fórmula:n mnnm

Q1: Isso pode ser alcançado com eficiência por um computador clássico (com bits aleatórios)?

P2: Isso pode ser alcançado com eficiência por um computador quântico?

Também estou interessado nas duas variantes a seguir:

V2: Você mostra todas as fórmulas com uma distribuição de probabilidade que fornece fórmulas satisfatórias duas vezes o peso de fórmulas insatisfatórias.

V3: você mostra onde o peso é o número de tarefas satisfatórias (aqui nos preocupamos apenas com o Q2).

Atualização: A resposta de Colins demonstra um algoritmo simples para a V3. (Errei ao supor que isso é classicamente difícil.) Deixe-me mencionar outra variante de todas as três perguntas:

Você especifica antecipadamente cláusulas e precisa amostrar subconjuntos aleatórios e satisfatórios das cláusulas de entrada.m

Gil Kalai
fonte
6
Pergunta muito interessante. Eu ficaria surpreso se houver um algoritmo conhecido para executar com eficiência qualquer uma dessas tarefas.
Giorgio Camerani

Respostas:

12

Existe um algoritmo simples para V3. Usarei a convenção de que existem possíveis cláusulas, portanto, fórmulas. (Isso é apenas para simplificar - se você não quiser que todas as cláusulas sejam consideradas válidas, isso não afetará o seguinte argumento.)2 8 n 3 8 n 3(2n)328n38n3

Escolha uma tarefa aleatória entre . Para cada uma das possíveis cláusulas verdadeiras nesta atribuição, inclua a cláusula com probabilidade . Cada fórmula aparecerá com probabilidade proporcional ao número de tarefas satisfatórias. A variante da cláusula é semelhante: escolha um conjunto de tamanho dentre as cláusulas . 7 N 3 1 / 2 φ m m 7 n 3{0,1}n7n31/2ϕmm7n3

Colin McQuillan
fonte
3
Isso é mencionado na introdução de Gerando instâncias de problemas satisfatórias , por D Achlioptas, C Gomes, H Kautz, B Selman.
Colin McQuillan