This week I worked on improving my understanding of the Parks Puzzle and exploring possible proof techniques to show that it is NP complete from two directions. I continued working on the Time Complexity chapters of \u201cIntroduction to The Theory of Computation\u201d by Michael Sipser to round out my theoretical understanding, while also solving many instances of the puzzle using an app on my phone. I came onto one general idea for the proof involving only \u2018AND\u2019 and \u2018OR\u2019 gadgets that I discussed with my advisor, who made some suggestions involving an \u2018IFF\u2019 gadget, which I am going to continue working on. I also received feedback on my literature review, which showed some significant problems that I corrected according to the grading rubric.<\/p>\n","protected":false},"excerpt":{"rendered":"
This week I worked on improving my understanding of the Parks Puzzle and exploring possible proof techniques to show that it is NP complete from two directions. I continued working on the Time Complexity chapters of \u201cIntroduction to The Theory of Computation\u201d by Michael Sipser to round out my theoretical understanding, while also solving many … Read more<\/a><\/p>\n","protected":false},"author":77,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80,93,19],"tags":[],"class_list":["post-3183","post","type-post","status-publish","format-standard","hentry","category-80","category-aditya-karan-kamireddy","category-student"],"_links":{"self":[{"href":"https:\/\/portfolios.cs.earlham.edu\/index.php\/wp-json\/wp\/v2\/posts\/3183","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/portfolios.cs.earlham.edu\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/portfolios.cs.earlham.edu\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/portfolios.cs.earlham.edu\/index.php\/wp-json\/wp\/v2\/users\/77"}],"replies":[{"embeddable":true,"href":"https:\/\/portfolios.cs.earlham.edu\/index.php\/wp-json\/wp\/v2\/comments?post=3183"}],"version-history":[{"count":1,"href":"https:\/\/portfolios.cs.earlham.edu\/index.php\/wp-json\/wp\/v2\/posts\/3183\/revisions"}],"predecessor-version":[{"id":3184,"href":"https:\/\/portfolios.cs.earlham.edu\/index.php\/wp-json\/wp\/v2\/posts\/3183\/revisions\/3184"}],"wp:attachment":[{"href":"https:\/\/portfolios.cs.earlham.edu\/index.php\/wp-json\/wp\/v2\/media?parent=3183"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/portfolios.cs.earlham.edu\/index.php\/wp-json\/wp\/v2\/categories?post=3183"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/portfolios.cs.earlham.edu\/index.php\/wp-json\/wp\/v2\/tags?post=3183"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}