Erudex sealErudex
Software & AI Engineering
All levels

Computational Complexity

Academic (University) preparation with worked examples, written practice and independent learning assessments.

Independent university-level study of Computational Complexity. This original curriculum draws on public academic subject descriptions; it is not an official faculty syllabus, university credit, accreditation or an Ivy League qualification. Topics covered: Machine models; Resource bounds; Reductions; Completeness. Time hierarchy; Space hierarchy; Padding; Diagonalization. NP completeness; CoNP; Polynomial hierarchy; Oracle machines. PSPACE completeness; Quantified formulas; Savitch theorem; Space-time tradeoffs. Randomized computation; RP; BPP; Derandomization. Boolean circuits; Circuit classes; Lower-bound methods; Nonuniform computation. Interactive proofs; Arithmetization; Probabilistically checkable proofs; Approximation hardness. Communication complexity; Query complexity; Fine-grained reductions; Complexity research problems. Projects use safe simulations, public datasets or textual analysis; specialist subject review is required. Includes lessons, supplementary YouTube tutorials, practical exercises, quizzes and free/paid practice tests. Erudex is independent, not affiliated with the source institution or awarding body. Its 80% learning checks are not official grades or university credit. Content requires qualified subject review before use as a complete teaching programme.

32h Certificate available
InternationalAcademic (University)Independent preparation

Curriculum

One complete track with its own final exam and certificate.

Independent university-level study of Computational Complexity. This original curriculum draws on public academic subject descriptions; it is not an official faculty syllabus, university credit, accreditation or an Ivy League qualification. Topics covered: Machine models; Resource bounds; Reductions; Completeness. Time hierarchy; Space hierarchy; Padding; Diagonalization. NP completeness; CoNP; Polynomial hierarchy; Oracle machines. PSPACE completeness; Quantified formulas; Savitch theorem; Space-time tradeoffs. Randomized computation; RP; BPP; Derandomization. Boolean circuits; Circuit classes; Lower-bound methods; Nonuniform computation. Interactive proofs; Arithmetization; Probabilistically checkable proofs; Approximation hardness. Communication complexity; Query complexity; Fine-grained reductions; Complexity research problems. Projects use safe simulations, public datasets or textual analysis; specialist subject review is required.

Machine models; Resource bounds; Reductions; Completeness

  • Foundational Machine Models, Resource Hierarchies, and Diagonalization Lab60 min
  • Nondeterminism, the Polynomial Hierarchy, and Space-Time Relations Lab60 min
  • Randomized Computation, Nonuniform Circuits, and Circuit Lower Bounds Lab60 min
  • Interactive Proofs, Hardness of Approximation, and Fine-Grained Complexity Lab60 min

Careers this prepares you for

    How you study

    Every lesson pairs an in-depth video with written notes, key takeaways, a hands-on lab, exercises and a quiz. Work at your own pace, then sit the final examination for your Erudex certificate.