Qual é a complexidade do Median-SAT?

14

Seja uma fórmula CNF com variáveis ​​e cláusulas . Deixe representar uma atribuição de variável conte o número de cláusulas satisfeitas por uma atribuição de variável para . Em seguida, defina Median-SAT como o problema de calcular o valor mediano de em todo . Por exemplo, se é uma tautologia, a solução para Median-SAT será pois, independentemente da atribuição, todas as cláusulas serão atendidas. No entanto, no caso den m t { 0 , 1 } n f φ ( t ) { 0 , , m } φ f φ ( t ) t { 0 , 1 } n φ m ¯ S A Tφnmt{0,1}nfφ(t){0,,m}φfφ(t)t{0,1}nφmSAT¯a solução para o Median-SAT pode estar em qualquer lugar entre e .m - 10m1

Essa pergunta surgiu quando eu estava pensando em duas extensões naturais do SAT, MAX-SAT e #SAT, e qual seria a dificuldade do problema resultante se elas fossem reunidas. Para MAX-SAT, precisamos encontrar uma atribuição de variável específica para maximizar o número de variáveis ​​satisfeitas por . Para #SAT temos que contar quantas atribuições satisfazer todas as cláusulas de . Essa variante acaba principalmente como uma extensão do #SAT (e de fato do #WSAT ), mas mantém um pouco do sabor do MAX-SAT, pois contamos o número de cláusulas satisfeitas em vez de apenas decidir se elas estão satisfeitas ou não.m φφmφ

Esse problema parece mais difícil que #SAT ou #WSAT. Para cada atribuição de variável #SAT decide o problema booleano de saber se essa atribuição satisfaz ou não, enquanto o Median-SAT determina "até que ponto" é satisfeito em termos do número de cláusulas que uma atribuição satisfaz.φφφ

Percebo que esse problema é um tanto arbitrário; calcular o número médio ou modo de cláusulas atendidas por cada atribuição de variável parece capturar a mesma qualidade. Provavelmente muitos outros problemas também.

Esse problema foi estudado, talvez sob um pretexto diferente? Quão difícil é comparado ao #SAT? Não está claro para mim a priori que o Median-SAT esteja contido no FPSPACE, embora pareça estar contido no FEXPTIME.

Huck Bennett
fonte
3
É em : para cada k m podemos contar o número de atribuições de satisfazer pelo menos k cláusulas utilizando um oráculo #P. FP#PFPSPACEkmk
Colin McQuillan
1
@ Colin transformar isso em uma resposta?
Suresh Venkat
Sim, isso daria uma boa resposta. Você poderia elaborar como consultar o oracle #P para verificar se as cláusulas são atendidas? Eu não conseguia descobrir como fazê-lo eficientemente. km
Huck Bennett
@Tsuyoshi, qual é a sua definição de SAT? Estamos permitindo a repetição de cláusulas? literais e / ou variáveis ​​em uma determinada cláusula? Porque se você não permitir a repetição de literais e / ou variáveis em um dado cláusulas você não pode ter uma fórmula CNF que é uma tautologia ..
Tayfun Pay
@ Tayfun - Na verdade, eu fiz essa pergunta, Tsuyoshi ajudou com uma edição menor. Você está certo sobre uma tautologia em uma fórmula CNF que exige literais repetidos. Qualquer variante do SAT seria interessante, CNF-SAT sem repetição de var nas cláusulas (caso em que as tautologias são impossíveis), ou talvez CIRCUIT-SAT de maneira mais geral. Não acho que essa escolha mude o sabor da pergunta.
Huck Bennett

Respostas:

13

Dada uma instância de SAT, um número inteiro e uma atribuição de variável, podemos decidir em tempo polinomial se exatamente k cláusulas são satisfeitas, simplesmente contando o número de cláusulas que são satisfeitas e testando se esse número é igual a k . Portanto, podemos calcular o número total de atribuições de variáveis ​​que satisfazem exatamente k cláusulas usando um oracle #P .kkkk

Assim como o Max-SAT, o Median-SAT pode ser calculado em tempo polinomial usando um oráculo Isto mostra que o problema é em F P # PF P S P A C E .#PFP#PFPSPACE

Colin McQuillan
fonte
Você está absolutamente correto. Este é um argumento muito claro, e acho bastante óbvio a partir da definição de #P. Eu aprendi alguma coisa
Huck Bennett
1
Deixe-me elaborar um pouco mais sobre isso: Colin está dizendo que, porque podemos determinar em tempo polinomial se uma determinada atribuição de variável satisfaz as cláusulas , podemos adivinhar incondicionalmente uma atribuição de variável e depois contar quantos caminhos de aceitação (ou seja, aceitar atribuições de variável) nesta consulta usava o oracle # P (por definição de # P ). Por iteração até k = 1 a m, que pode contar o número mediano de cláusulas satisfeitas em F P # P . k#P#PFP#P
Huck Bennett
3

Este problema pode ser resolvido usando de um oráculo para o MAJSAT.lgm+1

Seja o valor médio desejado para φ . Para k fixo , defina a fórmula ψ k, para que seja verdadeira para a atribuição x se s x satisfizer pelo menos k das cláusulas de φ . Observe que, dado φ na forma CNF e dado k , você pode facilmente construir ψ k na forma CNF em tempo polinomial.M(φ)φkψkxxkφφkψk

Agora, suponha que tivéssemos um oráculo para o MAJSAT. Consultando-lo na fórmula iria nos dizer se a maioria das atribuições fazer a fórmula ψ k verdade, ou equivalentemente, se M ( φ ) k . Portanto, para aprender M ( φ ) , aplique a pesquisa binária (comece com k = m / 2 e depois aumente ou diminua k de acordo com os resultados do oráculo). Após iterações lg m + 1 , a pesquisa binária revela o valor de M ( φ )ψkψkM(φ)kM(φ)k=m/2klgm+1M(φ). Cada iteração requer uma consulta ao nosso oracle para MAJSAT.

DW
fonte