Spring 2014

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.