Undergrad Complexity at CMU - Lecture 8: NP

Value of the Information & Strength of the Argument

The lecture provides substantial value by clearly explaining the motivation behind NP, connecting it to concrete problems and hypotheses. The argumentation is solid: the instructor builds from examples to formal definitions, and justifies the importance of NP via the Cook-Levin theorem and related conjectures. The discussion of ETH and SETH adds depth, showing how stronger assumptions lead to finer-grained hardness results. The presentation is rigorous and well-structured, with clear explanations of the verifier concept and its implications.

Scientific Rigor, Source Quality, Title Accuracy

The scientific rigor is high: the lecture is part of a university course taught by an expert, and the content aligns with standard textbooks (e.g., Sipser). The sources cited in the description are the course website and the instructor’s page, which are appropriate for further study. The title accurately reflects the content, focusing on the complexity class NP. The lecture does not rely on external sources but rather on established knowledge in the field.

The title accurately reflects the content: a lecture on the complexity class NP, covering its definition, motivation, and related hypotheses.

9/10

Lecture by a recognized expert in computational complexity, part of a university course, with rigorous definitions and references to standard results (Cook-Levin theorem, ETH, SETH). The content is technically accurate and well-structured.

Markers derived by PSI from the transcript: the creator did not define chapters.

• 00:00Introduction and motivation: recap of 3-SAT and the question of whether it can be solved in polynomial time.
• 05:00Discussion of the Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH).
• 10:00Example of a theorem using SETH: hardness of longest common subsequence problem.
• 15:00Introduction to NP: intuitive idea of problems with efficiently checkable candidate solutions.
• 20:00Examples of problems in NP: Hamiltonian path, 3-coloring, circuit SAT, composites.
• 25:00Formal definition of NP via verifiers: polynomial-time algorithm V that checks witnesses.
• 30:00Discussion of the asymmetry of NP: easy to certify membership, hard to certify non-membership.
• 35:00Proof techniques for showing a language is in NP: proving the yes and no cases.

• Course website — Official course page for 15-455, providing materials and references.
• Ryan O'Donnell's homepage — Instructor's academic page, with links to research and teaching.
• Panopto — Video platform used for recording and hosting the lecture.

• Sipser's Introduction to the Theory of Computation — Standard textbook covering NP and related topics, suggested reading for the course.