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 > 0CCM(C)M(C)CCCCM′M′c>0c>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)modpM(C)modpppCCNNlog2N−Blog2⁡N−BM(C)M(C)BBBBM(C)M(C)
Peço desculpas se a pergunta tem uma resposta conhecida, pois não sou um teórico da complexidade a propósito.
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.
É uma pergunta muito interessante. Para confirmar que M(C)modpM(C)modp é efectivamente difícil de computação, pode-se notar que a prova do teorema de Cook produz um mm fórmula -variável FF que seja satisfeita, ou de tal modo que M(F)=m−1M(F)=m−1 .
A questão pode ser reafirmada da seguinte maneira: pode haver um algoritmo de tempo polinomial que, dada uma fórmula F 3CNF FFF com mm variáveis, produza uma lista de números m/2Bm/2B modo que um desses números seja M(F)M(F) ?
sim, mm deveria ter sido o número de cláusulas no comentário acima.
é equivalente, porque se você tiver um algoritmo conforme descrito na publicação, poderá executá-lo em cada uma das 2log2m−B=m/2B2log2⁡m−B=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, log2m−Blog2⁡m−B bits de aviso são suficientes para especificar que a resposta correta é a i- é a iimaior das saídas do algoritmo, para alguns ii .
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∈Lx∈LM(f(x))=mM(f(x))=m
2) se entãox∈Lx∈LM(f(x))=m−1M(f(x))=m−1
onde é o número de cláusulas em .mmf(x)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.kkx1,…,xkx1,…,xk≤k−1≤k−1kkxi∈?Lxi∈?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+1K=2k+1x1,…,xKx1,…,xKLLKKF1,…,FKF1,…,FKmm
1) se e caso contrárioM(F1)=m−1M(F1)=m−1x1∈Lx1∈LM(F1)=m−2M(F1)=m−2
2) se e caso contrárioM(F2)=m⋅(m−1)M(F2)=m⋅(m−1)x2∈Lx2∈LM(F2)=m⋅(m−2)M(F2)=m⋅(m−2)
k) se e caso contrárioM(FK)=mK−1⋅(m−1)M(FK)=mK−1⋅(m−1)xK∈LxK∈LM(FK)=mK−1⋅(m−2)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 candidatosFFM(F)=M(F1)+⋯+M(Fk)M(F)=M(F1)+⋯+M(Fk)KKxi∈?Lxi∈?LmmM(F)M(F)M(F)M(F)kk2k2kM(F)M(F)M(F)≥niM(F)≥nin1,…,n2kn1,…,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+12k2k
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.FFO(1)k⋅mO(1)k⋅mmkmkkklogmlog⁡mloglogmlog⁡log⁡mlogm−O(1)log⁡m−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)]FPNP[O(logn)]O(logn)O(logn)f(x)=r1(g(r2(x))f(x)=r1(g(r2(x))r1r1r2r2mo(1)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)]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)]FPNP[O(logn)]=FPNP[o(logn)]PNP[O(logn)]=PNP[o(logn)]PNP[O(logn)]=PNP[o(logn)]FPNP[O(logn)]=FPNP[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:
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.
Deixe que C = f ( x ), e deixar que m seja o número de cláusulas C .
Encontre um i ∈ {0,…, m } tal que o valor g ( x , i , j ) seja constante independentemente de j ∈ {0,…, m }.
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.
Você poderia fornecer um link para a resposta da Dana?
@Turkistany: Ela excluiu sua resposta depois que eu publiquei a primeira revisão desta resposta. Acabei de remover uma referência a esta resposta.
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<10<c<1mmϕϕSSmcmcM(ϕ)∈SM(ϕ)∈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′<d0<d′<d≤n≤nNP⊆coNP/polyNP⊆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(ϕ)M(ϕ)ψ1,…,ψndψ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)(v,y1,…,ynd)yiyiψiψiv∈{0,1}dlogn+1v∈{0,1}dlog⁡n+100ndnd
Aceitamos se ou .ΓΓv=0v=0ψv(yv)=1ψ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∗(Γ)M∗(Γ)vvΓ(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.SSM∗(Γ)M∗(Γ)ψ1,…,ψndψ1,…,ψndψiψii∉Si∉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.SS≤nd′≤nd′ϕ1ϕ12m2m
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ϕ2vvvtvtvv[vt=1][vt=1]ttvvm/2t−1m/2t−1vvdlogn+1dlog⁡n+1mm
Finalmente, seja a saída de nossa redução.ϕ=ϕ1∧ϕ2ϕ=ϕ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,z)ϕϕvv(v,z)(v,z)vvN(v,z)=N(v,z)=ϕϕv,zv,z
M(ϕ)M(ϕ)(v,z)(v,z)vvé 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.)vvΓ(v,⋅)Γ(v,⋅)M∗(Γ)M∗(Γ)v=v=Γ(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 .SSM(ϕ)M(ϕ)|S||S|M∗(Γ)M∗(Γ)|S|≤nd′|S|≤nd′