Homework for Tuesday, January 28: Play the complexity guessing game and get into the Top 20 on the High Score table!
This course is an introduction to Theoretical/Mathematical computer science.
The title is “Recursive functions and complexity” which is an old fashioned term for
“Computable functions and complexity”.
Textbook: Sipser: Introduction to the theory of computation.
More information is available on Laulima.
Random comment: To show HALF-CLIQUE is NP-complete, we can proceed in two ways.
We can reduce CLIQUE to HALF-CLIQUE by splitting up into two cases: if k>m/2, add nodes not connected to anything until 2k= the new m, and if k<m/2, add some nodes connected to everything.
Alternatively, we can reduce 3SAT to HALF-CLIQUE directly. Namely, we note that the usual reduction of 3SAT to CLIQUE makes m=3k. To make (new m)=2(new k), we add some nodes, in fact k many, connected to everything. So (new m)=(old m)+k and (new k)=k+k.