Aproximando problemas # P-hard

9

Considere o problema clássico # P-complete # 3SAT, ou seja, contar o número de avaliações para tornar um 3CNF com variáveis ​​satisfatórias. Estou interessado na aproximação aditiva . Claramente, existe um algoritmo trivial para atingir o erro 2 n - 1 , mas se k < 2 n - 1 , é possível ter um algoritmo de aproximação eficiente, ou esse problema também é # P-difícil?n2n1k<2n1

user0928
fonte
Se , existe um algoritmo de politempo com erro aditivo k . Se k = 2 n / p o l y ( n ) , haveria um algoritmo aleatório poli-tempo com erro aditivo k . Quando k é significativamente menor (mas não polinomialmente pequeno), eu esperaria que fosse NP-hard, mas não # P-hard, pois a dureza #P geralmente depende de ser uma computação exata. k=2n1poly(n)kk=2n/poly(n)kk
Thomas
Você poderia fornecer referência para as duas primeiras reivindicações? Desculpe, eu sou um novato ...
user0928

Respostas:

10

Estamos interessados ​​em aproximações aditivas ao # 3SAT. ou seja, dado um 3CNF em n variáveis, conte o número de atribuições satisfatórias (chame a ) de até o erro aditivo k .ϕnak

Aqui estão alguns resultados básicos para isso:

Caso 1: k=2n1poly(n)

Aqui existe um algoritmo determinístico de politempo: Seja . Agora avalie ϕ em m entradas arbitrárias (por exemplo, as primeiras m lexicograficamente ). Suponha desses insumos satisfazer φ . Então, sabemos a ℓ, pois há pelo menos tarefas satisfatórias e a 2 n - ( m - )m=2n2k=poly(n)ϕmmϕaa2n(m)como existem pelo menos tarefas insatisfatórias. A duração deste intervalo é 2 n - ( m - ) - = 2 k . Portanto, se emitirmos o ponto médio 2 n - 1 - m / 2 + ℓ, isso está dentro de k da resposta correta, conforme necessário.m2n(m)=2k2n1m/2+k

Caso 2: k=2n/poly(n)

Aqui temos um algoritmo aleatório de politempo: Avalie em m pontos aleatórios X 1 , , X m{ 0 , 1 } n . Seja α = 1ϕmX1,,Xm{0,1}neε=k/2n. Nós produzimos2nα. Para que isso tenha erro no máximok, precisamos dek| 2nα-a| =2n| α-a/2n| ,que é equivalente a| α-a/2nα=1mi=1mϕ(Xi)ε=k/2n2nαk

k|2nαa|=2n|αa/2n|,
Por umlimite de Chernoff, P [ | α - a / 2 n | > Ε ] 2 - Ω ( m ε 2 ) , como E [ φ ( X i ) ] = E [ α ] = um / 2 n . Isso implica que, se escolhermos m = O ( 1 / ε|αa/2n|ε.
P[|αa/2n|>ε]2Ω(mε2),
E[ϕ(Xi)]=E[α]=a/2n (e garanta que m é uma potência de 2 ); então, com probabilidade de pelo menos 0,99 , o erro é no máximo k .m=O(1/ε2)=poly(n)m20.99k

Caso 3: para c < 1k=2cn+o(n)c<1

ψmnmk<2nm1n=O(m/(1c))ϕ=ψϕnmψbϕb2nmnma^|a^a|ka^ϕk

|ba^/2nm|=|aa^2nm|k2nm<1/2.
bba^ba^
Thomas
fonte