Aproximación de problemas # P-hard

9

Considere el problema clásico # P-complete # 3SAT, es decir, contar el número de valoraciones para hacer que un 3CNF con n variables sea satisfactoria. Estoy interesado en la aproximabilidad aditiva . Claramente, hay un algoritmo trivial para lograr2n1error 2 n - 1 , pero sik<2n1 , ¿es posible tener un algoritmo de aproximación eficiente, o este problema también es # P-difícil?

user0928
fuente
Si , entonces hay un algoritmo de poli-tiempo con error aditivo k . Si k = 2 n / p o l y ( n ) , entonces habría un algoritmo de politiempo aleatorio con error aditivo k . Cuando k es significativamente más pequeño (pero no polinomialmente pequeño), esperaría que sea NP-hard, pero no # P-hard, ya que la dureza #P generalmente depende de que sea un cálculo exacto. k=2n1poly(n)kk=2n/poly(n)kk
Thomas
¿Podría proporcionar una referencia para las dos primeras reclamaciones? Lo siento, soy un principiante ...
user0928

Respuestas:

10

Estamos interesados ​​en aproximaciones aditivas al # 3SAT. es decir, dado un 3CNF en n variables, cuente el número de asignaciones satisfactorias (llame a esto a ) hasta el error aditivo k .ϕnak

Aquí hay algunos resultados básicos para esto:

Caso 1: k=2n1poly(n)

Aquí hay un algoritmo determinista de poli-tiempo: Sea . Ahora evalúe ϕ en m entradas arbitrarias (p. Ej., Las primeras m entradas lexicográficamente ). Suponga que de estas entradas satisfacen ϕ . Entonces conocemos un ya que hay al menos asignaciones satisfactorias y un 2 n - ( m - )m=2n2k=poly(n)ϕmmϕaa2n(m)ya que hay al menos tareas insatisfactorias. La longitud de este intervalo es 2 n - ( m - ) - = 2 k . Entonces, si sacamos el punto medio 2 n - 1 - m / 2 + esto está dentro de k de la respuesta correcta, según sea necesario.m2n(m)=2k2n1m/2+k

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

Aquí tenemos un algoritmo aleatorio de poli-tiempo: Evalúe en m puntos aleatorios X 1 , , X m{ 0 , 1 } n . Deje α = 1ϕmX1,,Xm{0,1}nyε=k/2n. Producimos2nα. Para que esto tenga un error como máximoknecesitamosk| 2nα-a| =2n| α-a/2n| ,que es equivalente a| α-a/2nα=1mi=1mϕ(Xi)ε=k/2n2nαk

k|2nαa|=2n|αa/2n|,
Por unlímite de Chernoff, P [ | α - a / 2 n | > ε ] 2 - Ω ( m ε 2 ) , como E [ ϕ ( X i ) ] = E [ α ] = a / 2 n . Esto implica que, si elegimos m = O ( 1 / ε|αa/2n|ε.
P[|αa/2n|>ε]2Ω(mε2),
E[ϕ(Xi)]=E[α]=a/2n (y asegúrese de que m sea ​​una potencia de 2 ), entonces con una probabilidad de al menos 0.99 , el error es como 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
fuente