Considere el problema clásico # P-complete # 3SAT, es decir, contar el número de valoraciones para hacer que un 3CNF con variables sea satisfactoria. Estoy interesado en la aproximabilidad aditiva . Claramente, hay un algoritmo trivial para lograrerror 2 n - 1 , pero si , ¿es posible tener un algoritmo de aproximación eficiente, o este problema también es # P-difícil?
9
Respuestas:
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 .ϕ n a k
Aquí hay algunos resultados básicos para esto:
Caso 1:k=2n−1−poly(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=2n−2k=poly(n) ϕ m m ℓ ϕ a≥ℓ ℓ a≤2n−(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.m−ℓ 2n−(m−ℓ)−ℓ=2k 2n−1−m/2+ℓ k
Caso 2:k=2n/ p o l y (n)
Aquí tenemos un algoritmo aleatorio de poli-tiempo: Evalúe en m puntos aleatorios X 1 , ⋯ , X m ∈ { 0 , 1 } n . Deje α = 1ϕ metro X1, ⋯ , Xmetro∈ { 0 , 1 }norte yε=k/2n. Producimos2n⋅α. Para que esto tenga un error como máximoknecesitamosk≥| 2nα-a| =2n| α-a/2n| ,que es equivalente a| α-a/2nα = 1metro∑metroi = 1ϕ ( Xyo) ε = k / 2norte 2norte⋅ α k
Caso 3: para c < 1k=2cn+o(n) c<1
fuente
Aquí hay una referencia a Bordewich, Freedman, Lovász y Welsh que desarrolla este tema hasta cierto punto.
fuente