>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 15 [Text Version]
[About] [Contact] [Grades] [Projects] [Submit] [Schedule] [Syllabus] [Search ]
Session: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] (15) [16] [17] [18] [19] [20]
Thu Jun 8 13:03:00 PDT 2006

# 15

## Schedule

 Date Meet'g Study(2 pts) Bring(5 pts) Topic(5 pts) Notes Wed May 17 14 Chapter 10 sections 10.1 Ex Intractable Problems P & NP Mon May 22 15 Chapter 10 sections 10.2, 10.3 Ex NP-Complete Wed May 24 16 Chapter 10 sections 10.4, 10.5 Ex Graph Problems & TSP

## 10 NP-Completeness

### 10.2 An NP-Complete Problem 426

#### 10.2.1 The Satisfiability Problem 426

1. SAT::problem=Can this Boolean Expression be true.

This is the canonical NP_complete problem.

It is also the first problem ever proved to be NP-Complete.

In a sense SAT is about solving an equation:

2. x and (y or not x) and (z or not y) = true
1. If we have a good SAT algorithm then we can use it on not( E ) and it will find a solution iff E is false for some set of values for its variables.
2. When applied to not(E) failing to find a solution means that E is always true.
3. So SAT can be used to test for tautologies.

#### 10.2.2 Representing SAT Instances 427

1. Rename the variables as x1...
2. Encode them using binary subscripts.

#### 10.2.3 NP-Completeness of the SAT Problem 428

You might say that this theorem came from trying to find a way to code efficient ND solution as efficient deterministic solutions. However we end up failing. Instead we discover that SAT is as hard as any other NP problem.

#### Error on page 430 and 434 from web site

There is a condition U(Uniqueness) missing. It says (roughly) that for i,j there is only one Z such that y[i,j,Z]. It would look like
3. AND[i,j,W,Z]( NOT( y[i,j,W] AND y[i,j,Z] ). This takes polynomial time to express and is polynomial in length.

On page 434 we have

4. E[M,w] = S ^ N ^ F ^ U.

#### Ch 10.2.3 pp 428-434 -- SAT Problem encodes NTM

Could you please show a small example of how a boolean expression can be transformed into IDs like in 10.2.3?

We transform Boolean Expressions into Turing data in 10.2.2 above! !0.2.3 is about writing a Boolean expression that represents the complete operation of a TM from Start to Finish. Perhaps the simplest possible one would be a machine with to states q0 and qf which, on any data, moves to the right leaving the symbol alone and enters qf (and halts). More in class...

#### Ch 10.2 pp 428 -- SAT NP-complete

After reading I am still not sure why SAT is NP-complete can you please go over why SAT is NP-complete.

#### Class Exercise

You need to be able to express the idea of the proof as simple but clear paragraph of about 250(?) words. However, in the final, I do not expect you to reproduce all the details of what is going on.
1. Prove that there is a NTM that solves SAT in polynomial time -- it just guesses any satisfying assignment and checks it.
2. Starting with any NP problem we prove that there is a SAT problem that expresses it.
1. First note that we have a NTM that halts and solves the problem in p(n) steps for some polynomial of the length of the input.
2. We can rewrite the TM so that it never writes a Blank and never moves to theleft of the start position.
3. So the TM won't need to visit more than p(n) symbols.
4. Next note that we can encode the ID as a string with no more than p(n)+1 steps.
5. This code can be modelled by a slew of boolean variables ( (p(n)+1)^2 ??).
6. It is then easy to encode the starting and finishing states using the boolean variable.
7. Coding the transitions is harder but possible.
8. Adding a uniqueness coinstraint gives a large boolean expression that encodes the whole computation if and only if the expression is satisfied.

#### 10.2.4 Exercises for Section 10.2 434

##### Exercise 10.2.1 Boolean Expressions
Try truth tables to count that satisfying truth assignments.

### 10.3 A Restricted Satisfiability Problem 435

#### Exercise -- definitions

Define
1. Literal
2. Clause
3. CNF
4. k-CNF
5. CSAT
6. KSAT
7. 3SAT

#### Ch 10.3 pp -- Disjunctive Normal Form

It seems as though being able to determine the disjunctive normal form for a boolean function would trivially solve the SAT problem. Does this mean that determining the disjunctive normal form for a boolean expression is NP complete?

Since the disjunctive normal form lists the truth assignments and so solves SAT we can be sure that any mapping to disjunctive normal form will NOT take polynomial time. Notice that reducing to disjunctive normal form is not a problem in the technical sense so we can't say that it is NP-complete. However we can conclude that (if P!=NP) that the mapping must be expensive -- not polynomial.

By the way: there is a comparatively simple process for converting to disjunctive normal form [ logic_27_Tableaux.html ] -- but sometimes the tree grows wildly -- just as the theory of NP-completeness suggests.

#### Ch 10.3.2 pp 438 -- Intractable Problems

Could you please explain Theorem 10.12 I had trouble understanding the proof.

#### Theorem 10.13 Can reduce SAT to 3SAT in polynomial time

Take notes on the way that new variables are introduced in this proof.

#### Ch 10.3.2 pp 438 -- Converting Expressions to CNF

Why is E not equivalent to F in general if S is an extension of T?

Equivalence can hold between expressions that use different variables:

1. x+y is not equivalent to x (By definition)

#### Ch 10.3.3 pp 440 -- NP-Completeness of CSAT

Can you explain the trick introduced in Theorem 10.13 used to prove CSAT is NP-Complete.

Take note of the tricky use of extra variables!

#### Ch 10.3.3 pp 440-443 -- NP-completeness of CSAT

Is their an easier way to understand the Theorem 10.13 on page 440 then three pages of explanation.

I haven't seen a better proof/explanation. Doing some examples should help convince us that any SAT can be reduced to a 3SAT.

#### DO first part of Exercise 10.3.1 before continuing

What is is the CNF encoding (using extra variables) of
• *a) xy+xbar z
• b) wxyz+u+v
• c) wxy + xbar u v

Would you please go over the reduction of 3SAT to SAT? I have seen it twice and I am still a bit confused.

Actually we need to show that we can reduce SAT to 3SAT!. Because 3SAT is NP we can use Cook's theorem to show that 3SAT reduces to SAT.

#### Ch 10, ch10 pp 445 -- CNF to 3-CNF

Could you describe the steps that must be followed in order to convert a CNF expression into a 3-CNF expression? The objective of exercise 10.3.1 was to make such conversions, but I didn't quite understand how the book went about it.

#### Ch 10 pp 429 -- SAT and 3SAT

Could you explain the difference between SAT and 3SAT It seems that they are the same thing.

#### COMPLETE exercise 10.3.1 before continuing

You have the CNF for the following Boolean Expressions:
• *a) xy+xbar z
• b) wxyz+u+v
• c) wxy_xbar u v
Translate it into 3-CNF.

#### 10.3.5 Exercises for Section 10.3 446

##### Exercise 10.3.2 4TA-SAT
Look for a KISS trick reducing SAT to 4TA-SAT
##### Error in Exercise 10.3.3 from web sight
Three missing integer variables i,j,k : 1..n.

E[n] has clauses (x[i]+x[j]+x[j]) and (x_bar[i]+x_bar[j]+x_bar[k]).

##### Exercise 20.3.4 2SAT is in P
Try this for yourself for a time. No more than an hour and if then stuck search the web for "2SAT polynomial". I found a cool Power Point demo.... bring the URL in and demo it.

. . . . . . . . . ( end of section 15) <<Contents | End>>

## Next

[ 16.html ]

## Notes

(Ex): Do as many of the relevant exercises as you have time for. You may work in a team of up to 4 students and hand in one joint solution. Bring to class one written solution to an exercise. This must not be a solution to an exercise marked with an asterisk(*) to earn full credit. One of the authors will be invited to present the solution to the class -- failure will loose points. Students taking CS646 must hand in the solution to an exercise marked with an exclamation mark(!) to earn full credit.
(Study): Read & think about the assigned items. Submit one question by selecting the submit button at the top of the web page. To earn complete credit you need to do this at least 90 minutes before the start of class. Hints. Read each section twice -- once the easy bits and then the tough bits. Use a scratch pad and pencil as you read.
(Topic): To earn all the possible points you must: turn up on time, not leave early, present work when called upon, and take part in discussions.

1. GJ75::= See http://www.csci.csusb.edu/dick/cs546/14.html#GJ75.

# Standard Definitions

1. FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
2. ND::="Non-deterministic", a machine that can try out many possibilities and always guesses the right choice. Note: For a given problem a ND solution is simpler and easier to understand than a deterministic one. We study ND machines to discover how to use them as high-level designs for more complicated deterministic machines. Plus it's fun.
3. PDA::="Push down Automata", a machine with a finite control and a single stack for remembering intermediate data. Kind of like half a TM.
4. RJB::=The author of this document, [ ../index.html ]
5. |-RJB="Richard J Botting, Comp Sci Dept, CSUSB".
6. Schedule::= See http://www.csci.csusb.edu/dick/cs546/schedule.html.
7. Search::= See http://www.csci.csusb.edu/dick/cs546/lookup.php.
8. Syllabus::= See http://www.csci.csusb.edu/dick/cs546/syllabus.html, and also see [ syllabus.html ] (my generic syllabus).
9. TBA::="To Be Announced".
10. TM::="Turing Machine".
11. NTM::="Nondeterministic Turing Machine".
12. nondeterministic::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
13. DTM::="Deterministic Turing Machine".
14. runtime::=run_time,
15. run_time::="The number of steps a TM takes before it halts when start on a given input".
16. complexity::="The largest run_time for any word with a given length" , usually expressed as an assymptotic (Big-O) formula.
17. P::@problem=class of problems that a DTM can compute in polynomial_time.
18. NP::@problem=class of problems that a NTM can compute in polynomial_time.
19. polynomial_time::=An algorithm/TM is said to halt in polynomial time if the number of steps given n items of data is less than O(n^c) for some constant c.

# From Logic

20. LOGIC::= See http://www.csci.csusb.edu/dick/maths/logic_25_Proofs.html

21. (LOGIC)|- (ei): Existential instantiation -- if P is true of something then we can substitute a new variable for it.
22. (LOGIC)|- (eg): existential generalization -- if P is true of this thing then it is true of something!
23. (LOGIC)|- (given): a proposition that is assumed as part of a Let...End Let argument. Typically if A and B and C then D starts with assuming A,B, and C are given. They are called the hypotheses.
24. (LOGIC)|- (goal): a proposition that we wish to prove. Typically the part after the then in an if...then... result. This is called the conclusion.
25. (LOGIC)|- (def): By definition of a term defined above.
26. (LOGIC)|- (algebra): Either by using well known algebraic results, or by use a series of algebraic steps.
27. (LOGIC)|- (RAA): Reduce to absurdity. The end of a Let/Po/Case/Net that establishes the negation of the last set of assumptions/hypotheses.