Complexity Atlas
HE

Source library and methodology

Course sources determine notation and exam scope; textbooks provide independent mathematical checks.

1

Current lecturer slides

Notation, scope, and formal definitions

2

Merged course notes

Detailed course-aligned proofs

3

Current readers and assignments

Advanced coverage and assessed exercises

4

Textbooks

Independent mathematical verification and enrichment

5

Community summaries and transcripts

Intuition and supporting evidence

6

Unofficial/personal solutions

Draft leads only; independently re-solved

Handwritten lectures

Scanned pages with no usable text layer. Each lecture opens a side-by-side view: the page beside its transcription, with every line's position marked on the page.

Course summary

A typeset document read through two independent channels and reconciled between them. References cite a page.

Source
Complexity Summary.pdf
Pages
34
  1. p. 2K-tape (M) vs. Single-tape (M̂) Turing Machine
  2. p. 2Universal Machine
  3. p. 2Configuration of a Turing Machine
  4. p. 2DTime vs DSpace
  5. p. 3Time & Space constructible
  6. p. 3Hierarchy Sentences
  7. p. 4Deterministic vs. Nondeterministic
  8. p. 4Padding proof template
  9. p. 5NP – Witness Definition
  10. p. 5Polynomial-Time reductions
  11. p. 5Cook-Levin
  12. p. 5Hamilton
  13. p. 6Approximation Algorithm
  14. p. 6Randomized Algorithm
  15. p. 6Amplification
  16. p. 6Random Complexity Classes
  17. p. 7Space Complexity
  18. p. 7Configurations Graph
  19. p. 8Important Sentences
  20. p. 9NP Problems
  21. p. 12Polynomial-time Reductions
  22. p. 21Approximation Algorithms
  23. p. 24Randomized Algorithms
  24. p. 27Probability
  25. p. 29Space Complexity Problems
  26. p. 34Proving class closed under reduction
  27. p. 34Proving class is not closed under certain reduction

Exam bank

Scanned exams. They are printed and legible, so a citation is enough: which exam, which page.

  • 2025 · semester 2 · moed 1מאגר בחינות/נושא 131111 קבוצה 13111102 שנה 2025 סמסטר 2 מועד 1.pdf26 content pages · transcribed: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51
  • 2025 · semester 3 · moed 1מאגר בחינות/shalon_131111_2025_s3_g06_moed1.pdf18 content pages · transcribed: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23
  • 2025 · semester 1 · moed 1מאגר בחינות/נושא 131111 קבוצה 13111101 שנה 2025 סמסטר 1 מועד 1.pdf6 content pages · transcribed: 1, 3, 5, 7, 9, 11
  • 2025 · semester 3 · moed 2מאגר בחינות/shalon_131111_2025_s3_g06_moed2.pdf15 content pages · transcribed: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25
  • 2024 · semester 2 · moed 1מאגר בחינות/נושא 131111 קבוצה 13111102 שנה 2024 סמסטר 2 מועד 1.pdf11 content pages · transcribed: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21
  • 2024 · semester 1 · moed 1מאגר בחינות/נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf12 content pages · transcribed: 1, 3, 5, 7, 9, 11
  • 2024 · semester 3 · moed 1מאגר בחינות/נושא 131111 קבוצה 13111106 שנה 2024 סמסטר 3 מועד 1.pdf14 content pages · transcribed: 1, 3, 5, 7, 9, 11, 13
  • 2024 · semester 1 · moed 2מאגר בחינות/נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf6 content pages · transcribed: 1, 2, 3, 4, 5, 6
  • 2024 · semester 3 · moed 2מאגר בחינות/נושא 131111 קבוצה 13111106 שנה 2024 סמסטר 3 מועד 2.pdf12 content pages · transcribed: 1, 3, 5, 7, 9, 11
  • 2023 · semester 2 · moed 1מאגר בחינות/נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 1.pdf14 content pages · transcribed: 1, 3, 5, 7, 9, 11, 13
  • 2023 · semester 1 · moed 1מאגר בחינות/נושא 131111 קבוצה 13111101 שנה 2023 סמסטר 1 מועד 1.pdf12 content pages · transcribed: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
  • 2023 · semester 3 · moed 1מאגר בחינות/נושא 131111 קבוצה 13111106 שנה 2023 סמסטר 3 מועד 1.pdf12 content pages · transcribed: 1, 3, 5, 7, 9, 11
  • 2023 · semester 2 · moed 2מאגר בחינות/נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf7 content pages · transcribed: 1, 2, 3, 4, 5, 6, 7
  • 2023 · semester 1 · moed 2מאגר בחינות/נושא 131111 קבוצה 13111101 שנה 2023 סמסטר 1 מועד 2.pdf12 content pages · transcribed: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
  • exam-7ea213626aמאגר בחינות/מ-נושא 131111 סיבוכיות מועד 1.pdf13 content pages · transcribed: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23
  • exam-9b59d8b607מאגר בחינות/מ-נושא 131111 סיבוכיות מועד 2.pdf30 content pages · transcribed: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29