with No Comments

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 “Introduction to The Theory of Computation” 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 ‘AND’ and ‘OR’ gadgets that I discussed with my advisor, who made some suggestions involving an ‘IFF’ 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.

Leave a Reply