
{"id":4263393,"date":"2013-11-26T02:27:50","date_gmt":"2013-11-26T12:27:50","guid":{"rendered":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/?page_id=4263393"},"modified":"2019-09-30T15:30:15","modified_gmt":"2019-10-01T01:30:15","slug":"math-657","status":"publish","type":"page","link":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/teaching\/math-657\/","title":{"rendered":"Math 657 (Spring 2014)"},"content":{"rendered":"<p>Spring 2014<\/p>\n<p>Homework for Tuesday, January 28: Play the complexity guessing game and get into the Top 20 on the High Score table!<\/p>\n<p>This course is an introduction to Theoretical\/Mathematical computer science.<br \/>\nThe title is &#8220;Recursive functions and complexity&#8221; which is an old fashioned term for<br \/>\n&#8220;Computable functions and complexity&#8221;.<\/p>\n<p>Textbook: Sipser: Introduction to the theory of computation.<\/p>\n<p>More information is available on Laulima.<\/p>\n<p><strong>Random comment:<\/strong> To show HALF-CLIQUE is NP-complete, we can proceed in two ways. <\/p>\n<p>We can reduce CLIQUE to HALF-CLIQUE by splitting up into two cases: if k&gt;m\/2, add nodes not connected to anything until 2k= the new m, and if k&lt;m\/2, add some nodes connected to everything.<\/p>\n<p>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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 &#8220;Recursive functions and complexity&#8221; which is an old fashioned term for &#8220;Computable functions and complexity&#8221;. Textbook: Sipser: Introduction to the &hellip; <a href=\"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/teaching\/math-657\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Math 657 (Spring 2014)<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":3613486,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-4263393","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/pages\/4263393","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/comments?post=4263393"}],"version-history":[{"count":13,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/pages\/4263393\/revisions"}],"predecessor-version":[{"id":9098035,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/pages\/4263393\/revisions\/9098035"}],"up":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/pages\/3613486"}],"wp:attachment":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/media?parent=4263393"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}