I'm having problems trying to understand a powerpoint our teacher gave us. The topic is on the theory of NP-Completeness. My biggest questions are,
1. How does the author derive all the 8-22 statements simply from 8-21?
2. How does the author change the '&'s and '-->'s to 'v's from 8-22 to 8-23?
3. Why is x(1)=7 and x(2)≠7 alone? What does "input data" mean?
8-21
Transforming searching to SAT
Does there exist a number in { x(1), x(2), …, x(n) }, which is equal to 7? Assume n = 2. nondeterministic algorithm:
i = choice(1,2)
if x(i)=7 then SUCCESS
else FAILURE
8-22
i=1 v i=2
& i=1 → i≠2
& i=2 → i≠1
& x(1)=7 & i=1 → SUCCESS
& x(2)=7 & i=2 → SUCCESS
& x(1)≠7 & i=1 → FAILURE
& x(2)≠7 & i=2 → FAILURE
& FAILURE → -SUCCESS
& SUCCESS (Guarantees a successful termination)
& x(1)=7 (Input Data)
& x(2)≠7
8-23
CNF (conjunctive normal form) :
i=1 v i=2 (1)
i≠1 v i≠2 (2)
x(1)≠7 v i≠1 v SUCCESS (3)
x(2)≠7 v i≠2 v SUCCESS (4)
x(1)=7 v i≠1 v FAILURE (5)
x(2)=7 v i≠2 v FAILURE (6)
-FAILURE v -SUCCESS (7)
SUCCESS (8)
x(1)=7 (9)
x(2)≠7 (10)
Thanks in advance.