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 11 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.
Following the Election Day adjustments, the “Tuesday” cohorts are now the last ones in the schedule, and the week starts with the “Wednesday” cohorts.
|Day||"Wednesday" Cohort||"Thursday" Cohort||"Friday" Cohort||"Sunday" Cohort||"Monday" Cohort||"Tuesday" Cohort|
|Thu 5 Nov||Preparation||(Week 10)||(Week 10)||(Week 10)||(Week 10)||(Week 10)|
|Fri 6 Nov||Preparation||Preparation||(Week 10)||(Week 10)||(Week 10)||(Week 10)|
|Sat/Sun 7/8 Nov||Preparation||Preparation||Preparation||(Week 10)||(Week 10)||(Week 10)|
|Mon 9 Nov||Cohort Meeting||Preparation||Preparation||Preparation||(Week 10)||(Week 10)|
|Tue 10 Nov||Preparation||Cohort Meeting||Preparation||Preparation||Preparation||(Week 10)|
|Wed 11 Nov||Assessed Cohort Meeting||Preparation||Cohort Meeting||Preparation||Preparation||Preparation|
|Thu 12 Nov||Write-up Due||Assessed Cohort Meeting||Preparation||Cohort Meeting||Preparation||Preparation|
|Fri 13 Nov||Week 12||Write-up Due||Assessed Cohort Meeting||Preparation||Cohort Meeting||Preparation|
|Sat/Sun 14/15 Nov||Week 12||Week 12||Write-up Due||Assessed Cohort Meeting||Preparation||Cohort Meeting|
|Mon 16 Nov||Week 12||Week 12||Week 12||Write-up Due||Assessed Cohort Meeting||Preparation|
|Tue 17 Nov||Week 12||Week 12||Week 12||Week 12||Write-up Due||Assessed Cohort Meeting|
|Wed 18 Nov||Week 12||Week 12||Week 12||Week 12||Week 12||Write-up Due|
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.
After the Assessed Cohort Meeting, your Cohort Leader will select one problem that your cohort needs to write-up and submit. The write-up is due by 11:59pm on the day after your assessed cohort meeting (see the schedule above).
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.
The videos for this week are longer than in previous weeks (so please don’t wait to get started on them!), but include quite a bit of review material and are designed to get to a good understanding of the P=NP question.
You can play all the videos using this playlist, but don’t forget to take breaks: Week 11 Playlist
These videos are edited from these cs3102 classes (we don’t generally recommend watching the unedited versions, but they are available if you want to):
"Difficulty" of Functions (9:13)
RAM Model (7:00)
Shortest and Longest Path (11:16)
Tractable and Intractable Problems (6:38)
Questions about P and EXP (5:02)
Introducing NP (14:02)
Complexity Class NP (13:08)
Power of Nondeterministic Turing Machines (11:57)
Proving a Problem is in NP (7:50)
The P=NP Question (9:12)
Cook-Levin Theorem (17:02)
History of the Cook-Levin Theorem (8:31)
P=NP Recap (4:45)