ECE Ph.D. Qualifying Exam

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.

Back to QE CE question 2, August 2015

Back to ECE Qualifying Exams (QE) page

Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood