Undergrad Complexity at CMU - Lecture 18: NL-Completeness and Logspace Reductions

Undergrad Complexity at CMU - Lecture 18: NL-Completeness and Logspace Reductions

by Ryan O'Donnell

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Ryan O'Donnell 👥 14K 📅 July 3, 2017 ⏱ 80 min 👁 3K 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

NLlogspacereductionsST-PATHconfiguration graphSavitch's algorithmnondeterministic space

Summary

This lecture, part of Carnegie Mellon’s undergraduate computational complexity course, focuses on the class NL (nondeterministic logarithmic space) and its complete problem, ST-PATH. The instructor begins by reviewing the configuration graph of a nondeterministic Turing machine, which is central to proving containment results. He proves that NL is contained in P by constructing the configuration graph in polynomial time and then solving the reachability problem via BFS. He then proves that NL is contained in DSPACE(log^2 n) by using Savitch’s algorithm on the configuration graph, which can be implicitly accessed in log space. The lecture then introduces the concept of logspace reductions, which are necessary for defining NL-completeness. The main result is that ST-PATH is NL-complete under logspace reductions. The proof involves showing that any NL computation can be reduced to an ST-PATH instance via a logspace reduction that constructs the configuration graph on the fly. The lecture concludes with a discussion of the implications of these results, including the relationship between NL and other complexity classes.

167 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a thorough and rigorous treatment of NL-completeness and logspace reductions. The instructor builds the argument step by step, starting from the configuration graph and using it to prove containment results. The proofs are clear and well-motivated, with attention to technical details such as the need for a unique accepting configuration and the ability to check edges in log space. The argumentation is solid, and the lecture effectively conveys why ST-PATH is a natural complete problem for NL. The value of the information is high for students of complexity theory, as it covers fundamental concepts with precision.

108 words

Title / Content Match

The title accurately reflects the content: the lecture covers NL-completeness and logspace reductions, as promised.

Quality & Reliability

9/10

Lecture by a recognized expert in computational complexity, based on standard textbook material (Sipser), with rigorous proofs and clear explanations. The content is mathematically sound and well-structured.

Key Moments

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

Cited Sources

Concurring Sources

  • Sipser, Introduction to the Theory of Computation — Standard textbook covering NL and logspace reductions.

Contribution & Novelties

This lecture provides a clear and rigorous exposition of NL-completeness and logspace reductions, building on the configuration graph approach. It offers a pedagogical perspective that is valuable for students. The lecture does not present new research but synthesizes known results in an accessible manner.

Pour aller plus loin :

75 words

Radar Profile

The radar profile shows high scores across all dimensions, indicating a lecture that is information-dense, technically rigorous, and highly reliable. The balance between quantity and quality of information is excellent, with a strong emphasis on formal proofs.

Reliability 9/10