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 > 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) .
Peço desculpas se a pergunta tem uma resposta conhecida, pois não sou um teórico da complexidade a propósito.
fonte
Respostas:
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ãox∈L M(f(x))=m
2) se entãox∈L M(f(x))=m−1
onde é o número de cláusulas em .m f(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.k x1,…,xk ≤k−1 k xi∈?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+1 x1,…,xK L K F1,…,FK m
1) se e caso contrárioM(F1)=m−1 x1∈L M(F1)=m−2
2) se e caso contrárioM(F2)=m⋅(m−1) x2∈L M(F2)=m⋅(m−2)
...
k) se e caso contrárioM(FK)=mK−1⋅(m−1) xK∈L M(FK)=mK−1⋅(m−2)
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 candidatosF M(F)=M(F1)+⋯+M(Fk) K xi∈?L m M(F) M(F) k 2k M(F) M(F)≥ni n1,…,n2k nó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+1 2k
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.F O(1)k⋅m mk k logm loglogm logm−O(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)) r1 r2 mo(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
fonte
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.
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.
fonte
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<1 m ϕ S mc M(ϕ)∈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 d ≤ n n d ′0<d′<d nd ≤n nd′ ≤n NP⊆coNP/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 ψi v∈{0,1}dlogn+1 0 nd
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.S M∗(Γ) ψ1,…,ψnd ψi i∉S
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.S ≤nd′ M∗(Γ)
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.Γ ϕ1 m=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).ϕ1 2m
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).ϕ2 v vt v [vt=1] t v m/2t−1 v dlogn+1 m
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) v N(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 .S M(ϕ) |S| M∗(Γ) |S|≤nd′ nd′=mΩ(1)
fonte