Algebraic "NP vs. P" vs. "Boolean NP vs. P": Graduate Complexity Lecture 15 postscript at CMU

Value of the Information & Strength of the Argument

The lecture provides a clear and rigorous explanation of a subtle theorem in algebraic complexity. O’Donnell carefully corrects a previous statement, showing intellectual honesty and precision. The argumentation is solid, walking through the contrapositive and the key technical steps, including the handling of constants and the use of modular arithmetic. He also highlights the role of the generalized Riemann hypothesis, which adds depth. The value lies in clarifying the relationship between algebraic and Boolean complexity classes, which is crucial for researchers in the field.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with O’Donnell explicitly referencing the work of Burgisser and Karp-Lipton. He also mentions the course website for further materials. The title accurately reflects the content, which compares algebraic and Boolean versions of NP vs P. The presentation is well-structured, with a clear correction and proof sketch. No external sources are cited beyond the course materials, but the content is based on established research.

The title accurately reflects the content, which compares algebraic and Boolean versions of the P vs NP problem.

9/10

Lecture by a recognized expert in computational complexity, presenting a theorem with proof sketch, including corrections and caveats. The content is technically accurate and well-structured, though it assumes advanced background.

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

• 00:00Introduction and correction of the theorem from Lecture 15.
• 01:00Statement of the corrected theorem: NP not in P/poly implies algebraic NP/poly ≠ algebraic P/poly.
• 02:00Discussion of the contrapositive and the Karp-Lipton theorem.
• 03:00Proof idea: converting algebraic circuits for permanent to Boolean circuits.
• 04:00Assumptions about scalars and the need for modular arithmetic.
• 05:00Handling large constants and the role of the generalized Riemann hypothesis.
• 06:00Burgisser's result on eliminating constants and solving polynomial systems modulo primes.
• 07:00Conclusion and summary of the proof.

• Ryan O'Donnell's homepage — Course instructor's page with additional resources.
• Course website for 15-855 — Course materials and lecture notes.

• Burgisser, P. (2000). Completeness and reduction in algebraic complexity theory — Original work on algebraic complexity classes and the theorem discussed.