Week 12

Goals

This week we arrive at the most famous and foundational open problem in Computer Science (and, arguably, in all of Mathematics, and more questionably, perhaps of all human creative endeavor): is it substantially easier to verify the solution to a (certain very broad and common type of) problem, than it is to find that solution? (stated more formally in computer science as “P = NP?".

The main goals for Week 12 are to:

  • Understand how to talk about the hardness (“difficulty”) of computing functions.
  • Learn about a few examples of problems that appear to have surprisingly different difficulties.
  • Be able to talk about the tractability of problems, and understand what computer scientists categorize problems as tractable and intractable the way we do.
  • Understand precisely the definition of the complexity class NP, and two different ways of defining it.
  • Be able to prove a problem is in class NP.
  • Understand the P=NP question and its significance.
  • See how we might be able to make progress on determining if P=NP, and understand the Cook-Levin Theorem and the main idea behind its proof.

Schedule

Day “Monday” Cohort “Tuesday” Cohort “Wednesday” Cohort “Thursday” Cohort “Friday” Cohort
Wed 10 Nov Preparation (Week 11) (Week 11) (Week 11) (Week 11)
Thurs 11 Nov Preparation Preparation (Week 11) (Week 11) (Week 11)
Fri 12 Nov Preparation Preparation Preparation (Week 11) (Week 11)
Sat 13 Nov Prep Cohort Meeting Preparation Preparation Preparation (Week 11)
Sun 14 Nov Revision Prep Cohort Meeting Preparation Preparation Preparation
Mon 15 Nov Assessed Meeting Revision Prep Cohort Meeting Preparation Preparation
Tues 16 Nov Work on Writeup Assessed Meeting Revision Prep Cohort Meeting Preparation
Wed 17 Nov Writeup Due Work on Writeup Assessed Meeting Revision Prep Cohort Meeting
Thurs 18 Nov (Week 13) Writeup Due Work on Writeup Assessed Meeting Revision
Fri 19 Nov (Week 13) (Week 13) Writeup Due Work on Writeup Assessed Meeting
Sat 20 Nov (Week 13) (Week 13) (Week 13) Writeup Due Work on Writeup
Sun 21 Nov (Week 13) (Week 13) (Week 13) (Week 13) Writeup Due

Cohort Problems

These are the problems you should discuss in your Cohort Meeting, and everyone in your cohort should be prepared to present and discuss solutions to at the Assessed Cohort Meeting:

The problems are posted here and we think its a good idea to look at them early, but you’re not expected to be able to solve them until after doing the readings and watching the videos below.

Similarly to Week 5, for this week you will be assigned a new problem to solve for your write-up problem which you will need to solve on your own without any collaboration. This will be due 48 hours after your cohort meeting (instead of the usual 24 hours). This problem will expect you to do a reduction proof, similar to the ones in the cohort problems (but different enough to be new).

Reading

This week’s content is covered in several chapters in the TCS book. This is a lot of reading material, but you should consider it all “optional” this week - you are not expected to read these in detail, but should find the textbook a useful complement to the lecture content to have an alternate presenation of the materials and a refernce for some of the technical details that we do not cover in depth in the lectures.

Chapter 12: Efficient computation: An informal introduction [PDF]

Chapter 13: Modeling running time [PDF]

Chapter 14: Polynomial-time reducations [PDF]

Chapter 15: NP, NP completeness, and the Cook-Levin Theorem [PDF]

Chapter 16: What if P equals NP? [PDF]

Videos

You can play all the videos using this playlist, but don’t forget to take breaks: Week 12 Playlist (Note that in previous semesters this content was covered in Week 11.)

You can find recordings of the past cs3102 classes with most similar content here:

"Difficulty" of Functions (9:13)

RAM Model (7:00)

Shortest and Longest Path (11:16)

Satisfiability (14:45)

Tractable and Intractable Problems (6:38)

Polynomial Time Reductions (13:25)

Reducing 3SAT to LongestPath (16:54 total, with 9:30 of that optional [you may skip the proof from 3:35-13:05])

Longest Path Decision Problem (4:11)

Nondeterministic TMs and the class NP (23:25)

Optional Extra Videos. These videos are optional (and will duplicate some of the material in the other videos), but should increase your understanding of the meaning of class NP (and they also contain a song!).

(Optional) Introducing NP (14:02)

(Optional) Complexity Class NP (13:08)

Why do we care whether P=NP? (5:38)

NP Completeness (15:51)

Optional Extra Videos. These videos are optional but will give you deeper insight into NP Completeness and some of the historical context behind it and why we care about it.

(Optional) Cook-Levin Theorem (17:02)

(Optional) History of the Cook-Levin Theorem (8:31)

(Optional) P=NP Recap (4:45)