(Created page with "Category:ECE Category:QE Category:CE Category:problem solving Category:algorithms <center> <font size= 4> ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying...") |
|||
| Line 23: | Line 23: | ||
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 <math>Introduction\,to\,Algorithms</math>, section 34.5 for an example of this. | 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 <math>Introduction\,to\,Algorithms</math>, section 34.5 for an example of this. | ||
| − | [[ECE- | + | [[ECE-QE_CE1-2015|Back to QE CE question 2, August 2015]] |
[[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]] | [[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]] | ||
Latest revision as of 20:43, 7 March 2016
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.
