Computando qualquer informação sobre o Max-3SAT

26

Para uma fórmula 3CNF deixar ser o número máximo de cláusulas satisfeitos em qualquer atribuição para . Sabe-se que o Max-3SAT é difícil de aproximar (sujeito a P ≠ NP), ou seja, não há algoritmo polytime cuja entrada seja uma fórmula 3CNF e cuja saída seja o número modo que esteja dentro de um fator multiplicativo de , onde é uma constante positiva absoluta.M ( C ) C C M M ( C ) 1 + c M c > 0CM(C)CCMM(C)1+cMc>0

Eu acredito que também é NP-difícil calcular para qualquer módulo constante p . Gostaria de saber se a seguinte generalização comum desses dois fatos é verdadeira: Não existe um algoritmo polytime cuja entrada seja uma fórmula 3CNF C com cláusulas N e uma sequência de \ log_2 NB bits de aconselhamento e cuja saída seja M (C) . Aqui B é uma constante absoluta. Em palavras simples, não há algoritmo que calcule B bits de informação de M (C) .M(C)modppCNlog2NBM(C)BBM(C)

Peço desculpas se a pergunta tem uma resposta conhecida, pois não sou um teórico da complexidade a propósito.

Boris Bukh
fonte
1
Normalmente, um "conselho" pode depender apenas do tamanho da entrada. Acredito que sua intenção é que um "conselho" aqui possa depender da própria entrada. Não conheço uma terminologia padrão para essa noção.
Tsuyoshi Ito
9
É uma pergunta muito interessante. Para confirmar que M(C)modp é efectivamente difícil de computação, pode-se notar que a prova do teorema de Cook produz um m fórmula -variável F que seja satisfeita, ou de tal modo que M(F)=m1 .
Luca Trevisan
16
A questão pode ser reafirmada da seguinte maneira: pode haver um algoritmo de tempo polinomial que, dada uma fórmula F 3CNF FF com m variáveis, produza uma lista de números m/2B modo que um desses números seja M(F) ?
Luca Trevisan
2
sim, m deveria ter sido o número de cláusulas no comentário acima.
Luca Trevisan
9
é equivalente, porque se você tiver um algoritmo conforme descrito na publicação, poderá executá-lo em cada uma das 2log2mB=m/2B possíveis strings de aconselhamento, obtenha o máximo (ou menos se há colisões) respostas, e uma delas está correta. Se você tiver um algoritmo como no meu comentário acima, log2mB bits de aviso são suficientes para especificar que a resposta correta é a i- é a imaior das saídas do algoritmo, para alguns i .
Luca Trevisan

Respostas:

14

Aqui está um argumento de que, se você pudesse resolver o Max 3SAT em uma instância de cláusula m, com um número constante de bits de aconselhamento, a hierarquia polinomial entraria em colapso.

Corrija um problema NP-completo L. No teorema de Cook, conhecemos uma transformação f () das entradas x para L em fórmulas 3SAT f (x), de modo que

1) se entãoxLM(f(x))=m

2) se entãoxLM(f(x))=m1

onde é o número de cláusulas em .mf(x)

Também temos um teorema de Kadin, que diz que, se forem fornecidas entradas de um problema NP-completo, você terá um algoritmo de tempo polinomial que faz consultas a um oráculo NP e determina o resposta correta para os problemas NP , a hierarquia polinomial entra em colapso.kx1,,xkk1kxi?L

Suponha que tenhamos um algoritmo que resolva Max SAT nas entradas da cláusula m, com k bits de conselho. Usaremos o resultado de Hastad para construir um algoritmo como na premissa do teorema de Kadin.

Iniciar a partir do entradas para problema . Aplique o teorema de Cook a cada um deles. Após alguma normalização (que pode ser feita atribuindo pesos às cláusulas ou duplicando-os se não quisermos usar pesos), construímos as fórmulas onde, por um certo :K=2k+1x1,,xKLKF1,,FKm

1) se e caso contrárioM(F1)=m1x1LM(F1)=m2

2) se e caso contrárioM(F2)=m(m1)x2LM(F2)=m(m2)

...

k) se e caso contrárioM(FK)=mK1(m1)xKLM(FK)=mK1(m2)

Agora pegue a união das fórmulas, que foram construídos sobre as variáveis de conjuntos disjuntos, e chamá-lo . Portanto, temos e podemos "ler" a resposta para os problemas , olhando para a base- representação de . Se pudermos calcular com base em bits de conselho, significa que podemos encontrar valores de modo que um deles seja . Podemos então perguntar a um oráculo NP de maneira não adaptativa se para cada um dos valores candidatosFM(F)=M(F1)++M(Fk)Kxi?LmM(F)M(F)k2kM(F)M(F)nin1,,n2knós geramos. Portanto, conseguimos resolver instâncias de problemas NP-completos fazendo consultas não adaptativas a um oráculo NP, o que implica que a hierarquia polinomial entra em colapso.2k+12k

Usando o teorema de Hastad em vez do teorema de Cook, é possível empurrar o tamanho de para vez de , portanto, é possível pressionar para , e o número de bits de conselho . Entender o que acontece quando você recebe bits de conselho parece realmente difícil.FO(1)kmmkklogmloglogmlogmO(1)


Editado para adicionar: Krentel ( The Complexity of Optimization Problems . J. Comput. Syst. Sci. 36 (3): 490-509 (1988) ) provou que a computação do valor ótimo do problema máximo de clique está completa para , a classe de funções computáveis ​​em tempo polinomial com consultas a um oracle NP. A completude está em "reduções de uma consulta", na qual a função f é redutível para funcionar g se alguém puder escrever para o tempo polinomial computável e . Presumivelmente, o mesmo é verdadeiro para Max Clique. Agora, se Max Clique tivesse um algoritmo de tempo polinomial que produza uma lista deFPNP[O(logn)]O(logn)f(x)=r1(g(r2(x))r1r2mo(1)possíveis valores, ele estaria em , porque você poderia usar a pesquisa binária para encontrar o melhor com um número de consultas que é o log do tamanho da lista.FPNP[o(logn)]

Agora, se tivermos , definitivamente teríamos , que é o caso especial para problemas de decisão, e isso é conhecido pelos resultados de Wagner (aprimorando um resultado do Kadin que se aplica a um número constante de consultas), para recolher a hierarquia polinomial. Mas acho que pode ser sabido que realmente implicaria P = NP. Mas, de qualquer forma, os resultados de Krentel e Kadin-Wagner devem ser suficientes para dar outra prova do resultado de Andy Drucker. Agora, eu me pergunto se é realmente a mesma prova, ou seja, se o resultado Fortnow-Van Melkebeek funciona, explícita ou implicitamente, através de um argumento "simulando consultas NP com menos consultas NP".FPNP[O(logn)]=FPNP[o(logn)]PNP[O(logn)]=PNP[o(logn)]FPNP[O(logn)]=FPNP[o(logn)]

Um bom documento de pesquisa que explica o que está acontecendo com problemas de otimização e classes de consulta limitada:

http://www.csee.umbc.edu/~chang/papers/bqabh/npfsat.pdf

Luca Trevisan
fonte
8

Gostaria de indicar uma razão pela qual é difícil provar a dureza NP desse problema.

Em um comentário sobre a pergunta, Luca Trevisan deu uma boa maneira de reafirmar o problema: O seguinte problema é solucionável em tempo polinomial para cada constante k ? Dada uma fórmula CNF C com cláusulas m , produza no máximo m / k números inteiros para que um deles seja igual a M ( C ). Aqui k está relacionado com B por k = 2 B .

No entanto, vamos exigir mais. Nomeadamente, consideramos o seguinte problema: dada uma fórmula C do CNF , imprima dois números inteiros para que um deles seja igual a M ( C ). Denotamos esse problema por Π. O problema Π é pelo menos tão difícil quanto o problema original; portanto, se o problema original for NP-difícil, Π também deverá ser NP-difícil.

Observe que Π é um problema de relação. Um dos tipos mais simples de reduções que podem ser usados ​​para reduzir algum problema L a um problema de relação Π é uma redução de Levin em tempo polinomial, que é um caso especial de uma redução de Turing em tempo polinomial em que a redução chama o oráculo apenas para Π uma vez.

Afirmamos que P Π [1] = P. Isto obviamente implica que NP NP Π [1] a menos que P = NP, isto é, Π não seja NP-rígido sob a redutibilidade de Levin no tempo polinomial, a menos que P = NP.

Prova . Deixe L ∈P Π [1] , ou seja, existe uma redução de Levin de L para Π. Isso significa que existe um par ( f , g ) de uma função computável em tempo polinomial f : {0,1} * → {0,1} * que mapeia cada instância x do problema L para alguma fórmula CNF f ( x ) e um predicado computável em tempo polinomial g : {0,1} * × ℕ × ℕ → {0,1} tal que g ( x , i , j ) = L( x ) se i ou j for igual a M ( f ( x )). (Aqui L ( x ) = 1 se x é uma instância sim de L e L ( x ) = 0 se x é uma não instância.)

Construímos um algoritmo de tempo polinomial para L a partir disso, como segue. Seja x uma entrada.

  1. Deixe que C = f ( x ), e deixar que m seja o número de cláusulas C .
  2. Encontre um i ∈ {0,…, m } tal que o valor g ( x , i , j ) seja constante independentemente de j ∈ {0,…, m }.
  3. Emita esta constante g ( x , i , 0).

Na etapa 2, esse i existe sempre porque i = M ( f ( x )) satisfaz a condição. Além disso, esse algoritmo não pode gerar uma resposta errada porque g ( x , i , M ( f ( x ))) deve ser a resposta correta. Portanto, esse algoritmo resolve L corretamente. QED .

Se não me engano, a mesma idéia pode ser usada para provar que P Π [ k ( n )] ⊆DTIME [ n O ( k ( n )) ]. Isto implica que NP2P [ k ] para qualquer constante k, a menos que P = NP e NP2P [polilog] a menos que NP2DTIME [2 polilog ]. Entretanto, essa ideia por si só não parece excluir a possibilidade de Π ser NP-difícil sob a redutibilidade de Turing no tempo polinomial.

Tsuyoshi Ito
fonte
1
Você poderia fornecer um link para a resposta da Dana?
Mohammad Al-Turkistany
@Turkistany: Ela excluiu sua resposta depois que eu publiquei a primeira revisão desta resposta. Acabei de remover uma referência a esta resposta.
Tsuyoshi Ito
8

Acredito que podemos mostrar:

Afirmação. Há um valor tal que o seguinte é verdadeiro. Suponha que exista um algoritmo determinístico de politempo que, dada uma instância 3-SAT cláusula emita uma lista com no máximo valores, de modo que ; então a hierarquia polinomial entra em colapso.m ϕ S m c M ( ϕ ) S0<c<1mϕSmcM(ϕ)S

A prova usa os resultados de Fortnow e Santhanam sobre a inviabilidade da compactação de instância em seu artigo http://www.cs.uchicago.edu/~fortnow/papers/compress.pdf

Especificamente, olhando para a prova de Thm 3.1, acredito que se pode extrair o seguinte (verificarei novamente em breve):

"Teorema" [FS]. Existem números inteiros , de forma que o seguinte seja verdadeiro. Suponha que, em um politempo determinístico, seja possível transformar um OR de fórmulas booleanas cada comprimento , e em conjuntos de variáveis ​​disjuntos) em um OR de fórmulas (novamente disjuntos de variáveis ​​e de comprimento ), preservando satisfazibilidade / unsatisfiability da OU. Então e a hierarquia polinomial colapso.n dn n d 0<d<dndnndnNPcoNP/poly

A prova de nossa reivindicação será uma redução da tarefa de compactação OR mencionada no teorema acima [FS], para o problema da computação em lista . Suponha que seja uma lista de fórmulas cujo OR queremos compactar.M(ϕ)ψ1,,ψnd

Primeiro passo: defina um circuito de tamanho polinomial nas seqüências de entrada . Aqui, a cadeia codifica uma atribuição para , e codifica um número entre e .Γ(v,y1,,ynd)yiψiv{0,1}dlogn+10nd

Aceitamos se ou .Γv=0ψv(yv)=1

Agora deixe denotar o valor máximo , de modo que o circuito restrito seja satisfatório. (Essa quantidade é sempre pelo menos 0).M(Γ)vΓ(v,,,)

Suponha que possamos produzir eficientemente uma lista de valores possíveis para . Então a alegação é que, em nossa lista , podemos jogar fora todos os para os quais ; a lista resultante contém uma fórmula satisfatória se a original continha. Espero que isso fique claro por inspeção.SM(Γ)ψ1,,ψndψiiS

Conclusão: não podemos produzir de forma confiável uma lista de valores possíveis para , a menos que a poli hierarquia entre em colapso.SndM(Γ)

Segunda Etapa: Reduzimos do problema da computação em lista para o problema da computação em lista para instâncias 3-SAT .M(Γ)M(ϕ)ϕ

Para fazer isso, primeiro executamos a redução de Cook em para obter uma instância 3-SAT de tamanho . tem o mesmo conjunto de variáveis ​​que , junto com algumas variáveis ​​auxiliares. O mais importante para nossos propósitos, é satisfatório se for satisfatório.Γϕ1m=poly(nd)ϕ1Γϕ1(v,)Γ(v,)

Chamamos as `fortes restrições '. Damos a cada uma dessas restrições um peso de (adicionando restrições duplicadas).ϕ12m

Em seguida, adicionamos um conjunto de `restrições fracas ' que adicionam uma preferência para que o índice (definido na etapa 1) seja o mais alto possível. Há uma restrição para cada bit de , a saber . Deixamos que o -simo bit mais significativo do ter uma restrição de peso . Como tem o comprimento , esses pesos podem ser integrados (só precisamos pressionar para permitir que seja uma potência de 2).ϕ2vvtv[vt=1]tvm/2t1vdlogn+1m

Finalmente, seja a saída de nossa redução.ϕ=ϕ1ϕ2

Para analisar , seja o conjunto de variáveis ​​de , com como antes. Primeira nota que, dada qualquer atribuição a , pode-se inferir o valor de da quantidade (peso total das restrições satisfeitas com ). Isso decorre do design hierárquico dos pesos de restrição (semelhante a uma técnica da resposta de Luca). Da mesma forma, o valor máximo alcançável é alcançado por uma configuração que satisfaz todas as restrições fortes e onde (sujeito a isso)ϕ(v,z)ϕv(v,z)vN(v,z)=ϕv,z
M(ϕ)(v,z)vé o maior possível. Este é o maior índice para o qual é satisfatório, ou seja, . (Observe que sempre é possível, configurando all-0, satisfazer todas as restrições fortes, pois nesse caso é satisfatório.)vΓ(v,)M(Γ)v=Γ(v,)

Daqui resulta que, se recebermos uma lista de possíveis valores de , podemos derivar uma lista devalores possíveis de . Portanto, não podemos ter , a menos que a hierarquia poli diminua. Isso fornece a Reivindicação, uma vez que .SM(ϕ)|S|M(Γ)|S|ndnd=mΩ(1)

Andy Drucker
fonte