Computer Engineering(CE)

Question 1: Algorithms

August 2015

### Solution 1

This result is not particularly notable, since all it shows is that the 3-CNF problem is reducible to the clique problem in polynomial time. It is well known that both of these problems are NP-complete, and it is even the case that the professor's proof is commonly used to show that the clique problem is NP-complete. See Cormen's $Introduction\,to\,Algorithms$, section 34.5 for an example of this.

## Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett