{"id":1403,"date":"2003-11-28T11:23:53","date_gmt":"2003-11-28T18:23:53","guid":{"rendered":"https:\/\/blogs.ubc.ca\/genemoolee\/?p=1403"},"modified":"2019-07-16T16:04:12","modified_gmt":"2019-07-16T23:04:12","slug":"np-completeness-an-overview-lecture-notes-2003","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/genemoolee\/2003\/11\/28\/np-completeness-an-overview-lecture-notes-2003\/","title":{"rendered":"Lecture Notes: NP-Completeness: An Overview"},"content":{"rendered":"<h4>Kim, Y. E. and <span style=\"text-decoration: underline;\">Lee, G. M.<\/span> (2003). <a href=\"https:\/\/docs.google.com\/viewer?a=v&amp;pid=sites&amp;srcid=ZGVmYXVsdGRvbWFpbnxnZW5lbW9vbGVlfGd4OjMzZjI3ZThkNGYyODU0MDg\" target=\"_blank\" rel=\"noopener noreferrer\">NP-Completeness: An Overview<\/a>. Lecture Notes, November 2003.<\/h4>\n<p>This paper presents an overview of NP-complete problems. The theory of NP-completeness is important not only in the theoretical aspect but also in reality. First, we will take a look at the formal definition and some examples of NP-complete problems. Then, we will see how to prove a problem is NP-complete and how to cope with NP-complete problems.<\/p>\n<ul>\n<li><a href=\"https:\/\/www.slideshare.net\/GeneMooLee\/introduction-to-np-completeness\" target=\"_blank\" rel=\"noopener noreferrer\">Slides<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Kim, Y. E. and Lee, G. M. (2003). NP-Completeness: An Overview. Lecture Notes, November 2003. This paper presents an overview of NP-complete problems. The theory of NP-completeness is important not only in the theoretical aspect but also in reality. First, we will take a look at the formal definition and some examples of NP-complete problems. [&hellip;]<\/p>\n","protected":false},"author":51140,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[822902],"tags":[127043,45179,318535,45177],"class_list":["post-1403","post","type-post","status-publish","format-standard","hentry","category-teaching-materials","tag-algorithm","tag-computational-complexity","tag-lecture-notes","tag-np-completeness"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/genemoolee\/wp-json\/wp\/v2\/posts\/1403","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/genemoolee\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/genemoolee\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/genemoolee\/wp-json\/wp\/v2\/users\/51140"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/genemoolee\/wp-json\/wp\/v2\/comments?post=1403"}],"version-history":[{"count":3,"href":"https:\/\/blogs.ubc.ca\/genemoolee\/wp-json\/wp\/v2\/posts\/1403\/revisions"}],"predecessor-version":[{"id":1499,"href":"https:\/\/blogs.ubc.ca\/genemoolee\/wp-json\/wp\/v2\/posts\/1403\/revisions\/1499"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/genemoolee\/wp-json\/wp\/v2\/media?parent=1403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/genemoolee\/wp-json\/wp\/v2\/categories?post=1403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/genemoolee\/wp-json\/wp\/v2\/tags?post=1403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}