1
$\begingroup$

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.

  • 0
    The second "8-22" is supposed to read "8-23"?2011-04-11
  • 1
    On your question 2: $A\rightarrow B$ is equivalent to $\neg A \lor B$. Applying this yields the same clause labeled (2) twice; that's why there's one fewer clause in 8-23 than in 8-22. Also, applying this when $A$ is a conjunction yields a disjunction via $\neg(C\land D)=(\neg C)\lor(\neg D)$.2011-04-11
  • 0
    Thanks joriki! Now if I only knew what `choice` meant...2011-04-12

1 Answers 1