Transcript Hardness Result for MAX-3SAT - CS

Hardness Result for MAX-3SAT
This lecture is given by:
Limor Ben Efraim
1
3Sat CNF formula: a formula  of n variables (xi) given by
m clauses (Cj), each clause contains exactly 3 literals.
Max-3Sat:
Given: 3Sat CNF formula.
Goal: Find an assignment x that maximize the number of
satisfied clauses.
Hastard (1997), Khot(2002): For any constant  > 0 , it is
NP Hard to distinguish whether a MAX-3SAT instance is
satisfiable or there is no assignment that satisfies ⅞+
fraction of the clauses.
Fact: Any random assignment satisfies 7/8 from the
clauses.
2
Max-3Lin-2:
Given: a system of linear equations over Z2, exactly
3 variables in each equation.
Goal: Find an assignment that maximize the
number of satisfied equations.
We saw
MAX-3Lin-2
Gap(½+,1-)
MAX-3Sat
Gap(⅞+,1-)
4 gadget
3
Label Cover - Reminder
Each vertex V
is a set of u
variables.
…
…
Each vertex
W is a set of
u clauses
Bipartite graph


Constraints
Functions
When an assignment  to LC satisfies the edge (V,W)?
If  satisfies W, and (V) is a restriction of (W).
4
type-0 block
0 is the family of all
type-0 blocks
A set of Tu clauses and u variables.
type-1 block
A set of (T+1)u clauses.
1 is the family of all
type-1 blocks
Given W 2 1 (V 2 0):
MW (MV) – the set of all satisfying assignments to W (V).
Given W 2 1 (V 2 0), how many satisfying assignments
there are ?
Answer: At most 7(T+1)u (2u7Tu) values.
5
When a type-0 block V is a sub block of type-1 block W ?
If we can replace u clauses {ci| i=1,2,…u} in W by u
variables {xi| i=1,2,…,u} in V such that the variable xi is in
the clause ci for 1 · i · u.
V,W:MW ! MV is the operation of taking a sub assignment.
6
Label Cover +
…
Each vertex
W is in 1
…
Bipartite graph
Each vertex V
is in 0
(V,W) 2 E(LG+) if V is a sub-block of W.
When an assignment  to LC+ satisfies the edge (V,W)?
If  satisfies both V and W, and V,W((W))=(V).
7
Theorem: It is NP Hard to distinguish between the
following two cases:
YES: There is an assignment  that satisfies every edge
in the graph
NO: No assignment can satisfies more that 2-(u)
of the edges
8
Lemma: W 2 1. Let ,’ 2 MW. If V is a random sub-block
of W then
PrV [V,W()=V,W(’)] · 1/T
Proof: ,’ differ at least on one clause. For a choice of a
random sub-block V, one replaces at random u clauses
out of (T+1)u clauses in W.
With probability · 1/T each different clause is replaced.
Corollary: W 2 1. Let 0   µ MW and  2 . If V is a
random sub block of W then
PrV [8 ’ 2 , ’  , V,W()  V,W(’)] ¸ 1-||/T
9
The Smoothness Lemma: For any set 0   µ MW
Proof:
10
Our Plan
Label Cover + with smoothness property.
3Sat CNF formula
If there is a satisfiable assignment to the Label Cover+
The 3Sat CNF formula is satisfiable.
If the Label Cover+ is 2-(u) satisfiable
11
The 3Sat CNF formula is · ⅞+ 8 >0
satisfiable.
Long Code
FV is the set of all functions f:MV! {-1,1}.
FW is the set of all functions f:MW! {-1,1}.
Long code of an assignment x 2 MV is the
mapping A:FV ! {-1,1} where A(f)=f(x).
|V|
Size: 22
12
Building…
V
…
W
…
AW
AV
We will replace each vertex W (V) in a set of boolean
variables, a variable for each bit of AW (AV), the long
code of W (V).
(W,f) ! XW,f. (V,f) ! XV,f.
13
Building - Continue
What are the clauses ?
To answer this, we define a test for each (W,V) 2 E(LC+)
V is a sub block of W
14
The test
Pick a block W 2 1
Pick a random sub-block V of W.
Let  = V,W
Let A,B be the supposed long codes of supposed
satisfying assignment to the blocks V,W resp.
Pick a function f:MV ! {-1,1} with the uniform probability.
Pick a function g:MW ! {-1,1} with the uniform
probability.
15
Define a function h:MW ! {-1,1} independently 8 y 2 MW
if f((y))=1 then h(y)=-g(y)
if f((y)=-1 then:
Accept unless A(f)=B(g)=B(h)=1.
Equivalent: Accept if the clause XV,f Ç XW,g Ç XW,h is
satisfiable
:{0,1} !{1,-1}
(x)=(-1)x
16
How many clauses we got ?
Polynomially in n for constant u !!!
Completeness
This test has perfect completeness.
If f(y|V)=1, by definition one of g(y),h(y) will be -1
B(g)=-1 or B(h)=-1.
If f(y|V)=-1, we have A(f)=-1.
17
Fourier Analysis
Reminder: FV is the set of all functions f:MV! {-1,1}.
Orthonormal basis to FV is:
(f)= x 2  f(x) 8  µ {-1,1}V. v=|V|.
The inner product of 2 functions A,B is
v
-2
(A,B)=2 f 2 FV A(f)B(f)
18
Fourier Analysis-Continue
Lemma: For any f,g 2 FV and , µ {-1,1}V:
1. (fg)=(f)(g)
2. (f)(f)=M (f).
Lemma:
1. Ef[(f)]=0
2. Ef[A(f)]=0
8  µ {-1,1}V ,   ;.
Parseval’s Formula:
19
Soundness
(f,g),(f,h) are
The acceptance criteria can be written as:
independent
Ef,g,h[ 1-⅛ (1+A(f)) (1+B(g)) (1+B(h)) ] =
⅞ - ⅛ [ Eg,h(B(g)B(h)) + Ef,g,h ( A(f)B(g)B(h) ) ]
We will show that each term · O()
For the rest of the proof fix T=
20
Eg,h,[B(g)B(h)]
21
sx is the number
of y 2  s.t. y|V=x
22
Pr[sx=1] ¸ 1-
23
24
e(x) · 1-
Ef,g,h,[A(f)B(g)B(h)]
25
Lemma: For any ,
Proof: the left size is equal to
26
27
Cauchy-Schwartz
inequality
E[X]2 · E[X2]
28
Cauchy-Schwartz
inequality
Goal: to see that this is bounded by O()
29
Reminder
Label Cover+
3Sat CNF Formula
Given assignment to the 3Sat-CNF formula
We can find an assignment to the Label Cover+
30
Goal: to see that if the assignment satisfies
¸ ⅞+O() of the clauses
Then we can find an assignment that satisfies
¸ 2-(u) of the edges.
The Folding Mechanism
Goal: To make sure that A(f)=-A(-f) 8 f.
Action: Given A: FU ! {-1,1}, define A’: for every pair (f,-f)
selecting one of (f,-f).
IF:
IF:
31
f is selected (A’(f),A’(-f))=(A(f),-A(f))
-f is selected (A’(f),A’(-f))=(-A(-f),A(-f))
We will assume all our long codes are of the
folding mechanism !!!
32
We will create an assignment to Label Cover+ based on
33
By the folding
lemma ,  ;
34
Previous theorem
on Label Cover+
For the choice
Summary
Label Cover +
Gap(2-(u),1)
Max-3Sat
Gap(⅞+,1)
Long Code +
Testing
FIN
35