# CSE 417 Assignment #5

Winter 2000

### Due: Friday, March 10, 2000.

Read the Manber text, sections 10.1 and chapter 11.

- A
**triangle** in a undirected graph G is a triple of
vertices {u,v,w} of G such that all three of (u,v), (v,w), (u,w) are edges
in G. Show that the problem TRIANGLE={< G > | G contains a triangle}
is in P.
- Manber's text: page 370, problem 11.1
- Here you will show that 4-SAT is NP-complete
- Show that the problem 4-SAT is in NP.
- Show a polynomial-time mapping reduction from 3-SAT to 4-SAT.

- Use the fact that 3-color is NP-complete to prove that the
following problem: COLOR={< G,k >| G is k-colorable} is NP-complete.
- Why is the following not a proof that P is different from NP?
We can decide the SAT problem using the following algorithm:
Given a formula F in n variables, try all 2
^{n} truth assignments
and see if there is any assignment that makes F true. If there is one, then
accept, else reject. This algorithm takes at least 2^{n} time
in the worst case and since 2^{n} is not polynomial in n, this
is not polynomial time.
- (Bonus) Manber's text: page 371, problem 11.13