Complexity Atlas
HE
What was asked, and how often

Exam atlas

Every sitting the course has held since 2018, taken apart into questions and joined back together: what recurred, from which sitting, and what is still being asked. Closed and open questions are counted separately.

30sittings
2018–2026exam years
251closed questions
57open questions
216with readable text
23recurring questions

The same proof with a class or a constant swapped. This is what recurrence usually looks like in this course.

  1. 3 sittingsClosed questions2025–2026Computed match

    נסמן C 1= c 1DTime (n (2 c) ), C 2=DTime (2 (n 6) ), C 3= c 1DTime (n n c ). איזו מהטענות הבאות היא החזקה ביותר הידועה כנכונה.

    • 2026 Semester B Moed AQ 3Verified
    • 2026 Semester B Moed BQ 7Transcribed1
    • 2025 Summer semester Moed BQ 1Transcribed1
    Source pages (2)· 1 sitting without one
    The page the question was read from — 2026 Semester B Moed B · p. 112026 Semester B Moed B · p. 11The page the question was read from — 2025 Summer semester Moed B · p. 32025 Summer semester Moed B · p. 3
    Time, space, and classesLessons 2, 3, 18
  2. 3 sittingsClosed questions2023–2026Computed match

    עבור 0< <1 נתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A * עבורן קיימת מכונת טיורינג דטרמיניסטית M וקיים פולינום p כך שלכל x *, M רצה על x בזמן לכל היותר p(|x|) וכמו כן לכל x *, אם x A אז r \0,1\ p(|x…

    • 2026 Semester B Moed AQ 6Verified
    • 2026 Semester B Moed BQ 5Transcribed1
    • 2023 Semester B Moed AQ 4Transcribed1
    Source pages (2)· 1 sitting without one
    The page the question was read from — 2026 Semester B Moed B · p. 72026 Semester B Moed B · p. 7The page the question was read from — 2023 Semester B Moed A · p. 52023 Semester B Moed A · p. 5
    Turing machines and modelsNP, verifiers, and nondeterminismRandomization and probabilityLessons 1, 2, 4, 5, 12, 13
  3. 2 sittingsOpen questions2025–2026Computed match

    תהאנה A,B Σ* שפות. רדוקציית זמן מעריכי מ A ל B היא מכונת טיורינג דטרמיניסטית M המקיימת את שתי התכונות הבאות. ● קיים c 1 כך שלכל x Σ* מתקיים timeM(x) O(2 |x| c). ● לכל x Σ* מתקיים x A אם ורק אם M(x) B. עבור כל אחת מהטענות…

    • 2026 Semester B Moed BQ 2Transcribed2
    • 2025 Summer semester Moed AQ 2Transcribed1
    Source pages (3)
    The page the question was read from — 2026 Semester B Moed B · p. 232026 Semester B Moed B · p. 23The page the question was read from — 2026 Semester B Moed B · p. 272026 Semester B Moed B · p. 27The page the question was read from — 2025 Summer semester Moed A · p. 172025 Summer semester Moed A · p. 17
    Turing machines and modelsReductions and Cook–LevinLessons 1, 2, 6, 7
  4. 2 sittingsClosed questions2026Computed match

    נתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A * עבורן קיימת מכונת טיורינג אי-דטרמיניסטית M וקיים פולינום p כך שלכל x *, אם x A אז כל ריצה של M על x מקבלת ועוצרת אחרי לכל היותר p(|x|) צעדים, וגם אם x A…

    • 2026 Semester B Moed AQ 8Verified
    • 2026 Semester B Moed BQ 6Transcribed1
    Source pages (1)· 1 sitting without one
    The page the question was read from — 2026 Semester B Moed B · p. 92026 Semester B Moed B · p. 9
    Turing machines and modelsNP, verifiers, and nondeterminismLessons 1, 2, 4, 5
  5. 2 sittingsClosed questions2024–2025Computed match

    שפה A ניתנת להכרעה ע"י מכונת טיורינג דטרמיניסטית שמשתמשת במקום O(n 2) לקלט באורך n. שפה B ניתנת לרדוקציה לשפה A ע"י מ"ט דטרמיניסטית בזמן O(n 3) לקלט באורך n. מהי המחלקה הקטנה ביותר ביחס להכלה שאליה ידוע שהכלה שאלייה שייכ…

    • 2025 Semester A Moed AQ 1Transcribed1
    • 2024 Semester A Moed AQ 2Transcribed1
    Source pages (2)
    The page the question was read from — 2025 Semester A Moed A · p. 32025 Semester A Moed A · p. 3The page the question was read from — 2024 Semester A Moed A · p. 32024 Semester A Moed A · p. 3
    Turing machines and modelsTime, space, and classesReductions and Cook–LevinLessons 1, 2, 3, 6, 7, 18
  6. 2 sittingsClosed questions2025Computed match

    נתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A Σ* עבור קיימת מכונת טיורינג אי-דטרמיניסטית M וקיימים c 1 כך שלכל x Σ*, אם x A אז קיימת ריצת M על x העוצרת אחרי לכל היותר |x| c צעדים, וגם אם x A אז בכל רי…

    • 2025 Summer semester Moed AQ 7Transcribed1
    • 2025 Summer semester Moed BQ 4Transcribed1
    Source pages (2)
    The page the question was read from — 2025 Summer semester Moed A · p. 92025 Summer semester Moed A · p. 9The page the question was read from — 2025 Summer semester Moed B · p. 72025 Summer semester Moed B · p. 7
    Turing machines and modelsTime, space, and classesNP, verifiers, and nondeterminismLessons 1, 2, 3, 4, 5, 18
  7. 2 sittingsOpen questions2025Computed match

    נגדיר את בעיית האופטימיזציה הבאה, WMAXSAT. קלט: נוסחה φ בצורת CNF שבה בכל הסגר מופיעים 3 משתנים שונים בדיוק. ופונקציית משקל w המתאימה משקל חיובי לכל הסגר בנוסחה. מטרה: למצוא השמה המקיימת כי משקל ההסגרים המסופקים הוא מקסי…

    • 2025 Summer semester Moed AQ 3Transcribed1
    • 2025 Summer semester Moed BQ 3Transcribed1
    Source pages (2)
    The page the question was read from — 2025 Summer semester Moed A · p. 212025 Summer semester Moed A · p. 21The page the question was read from — 2025 Summer semester Moed B · p. 232025 Summer semester Moed B · p. 23
    NP, verifiers, and nondeterminismApproximation algorithmsLessons 4, 5, 9, 10, 11
  8. 2 sittingsClosed questions2025Computed match

    עבור 1<α<0 נתונות מחלקות הסתביכויות הבאות. I. המחלקה C 1 היא כל השפות A Σ* עבורן קיימת מכונת טיורינג דטרמיניסטית M הרצה בזמן פולינומי בגודל הקלט x Σ*, כך שלכל אם x A אז Pr r 0,1 p(|x|) [M(x,r) accepts] α וגם אם x A אז Pr…

    • 2025 Summer semester Moed AQ 6Transcribed1
    • 2025 Summer semester Moed BQ 3Transcribed1
    Source pages (2)
    The page the question was read from — 2025 Summer semester Moed A · p. 72025 Summer semester Moed A · p. 7The page the question was read from — 2025 Summer semester Moed B · p. 52025 Summer semester Moed B · p. 5
    Turing machines and modelsRandomization and probabilityLessons 1, 2, 12, 13
  9. 2 sittingsClosed questions2023–2024Computed match

    ע"י המחלקה NP CoNP", ניתן להתמקד, לשם פשטות, בפונקציות הצפנה f משמרות- אורך f:0,1 n 0,1 n, ומגדירים שפה מתאימה L. חיוני שהפונקציה f תהיה חח"ע כדי:

    • 2024 Summer semester Moed AQ 2Transcribed1
    • 2023 Summer semester Moed AQ 5Transcribed1
    Source pages (2)
    The page the question was read from — 2024 Summer semester Moed A · p. 32024 Summer semester Moed A · p. 3The page the question was read from — 2023 Summer semester Moed A · p. 52023 Summer semester Moed A · p. 5
    NP, verifiers, and nondeterminismLogspace and NLLessons 4, 5, 14, 15, 16, 17
  10. 2 sittingsClosed questions2024Computed match

    נתאר להלן רדוקציה מ- 3-SAT ל- IS (תזכורת: IS היא שפת הזוגות <G,k> של גרף ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k). הרדוקציה: בהינתן קידוד של נוסחה φ מצורת 3-CNF עם m הסנרים נחזיר גרף G ואת המספר m. הגרף G יונדר כל…

    • 2024 Semester A Moed AQ 7Transcribed1
    • 2024 Semester A Moed BQ 7Transcribed1
    Source pages (2)
    The page the question was read from — 2024 Semester A Moed A · p. 72024 Semester A Moed A · p. 7The page the question was read from — 2024 Semester A Moed B · p. 42024 Semester A Moed B · p. 4
    NP, verifiers, and nondeterminismReductions and Cook–LevinNP-complete problemsLessons 4, 5, 6, 7, 8
  11. 2 sittingsClosed questions2024Computed match

    נסתכל על 3 הבעיות הבאות: בעיית ההכרעה של SAT: בהינתן נוסחה בוליאנית בצורת CNF – האם הנוסחה ספיקה. בעיית החיפוש של SAT: בהינתן נוסחה בוליאנית בצורת CNF – למצוא השמה מספקת אם יש כזו או להודיע "לא" אם אין לנוסחה השמה מספקת.…

    • 2024 Semester A Moed AQ 9Transcribed1
    • 2024 Semester A Moed BQ 9Transcribed1
    Source pages (2)
    The page the question was read from — 2024 Semester A Moed A · p. 72024 Semester A Moed A · p. 7The page the question was read from — 2024 Semester A Moed B · p. 52024 Semester A Moed B · p. 5
    Turing machines and modelsNP, verifiers, and nondeterminismLessons 1, 2, 4, 5
  12. 2 sittingsClosed questions2024Computed match

    בהוכחת משפט קוק-לוין שראינו בשיעור, ייצגנו ריצה של מכונה M על קלט (x,w) על ידי טבלה T M,x. במהלך ההוכחה, בנינו טבלאות אמת עבור תאים שונים בטבלה והמרנו אותן לצורת CNF. נניח שמספר המצבים ב- M הוא 10 ושמספר התוויים בא"ב העב…

    • 2024 Semester A Moed AQ 6Transcribed1
    • 2024 Semester A Moed BQ 6Transcribed1
    Source pages (2)
    The page the question was read from — 2024 Semester A Moed A · p. 52024 Semester A Moed A · p. 5The page the question was read from — 2024 Semester A Moed B · p. 42024 Semester A Moed B · p. 4
    Turing machines and modelsNP, verifiers, and nondeterminismReductions and Cook–LevinLessons 1, 2, 4, 5, 6, 7
  13. 2 sittingsClosed questions2024Computed match

    נתונות שלוש מחלקות סיבוכיות: C 1 = DSpace(n 5) , C 2 = NSpace(n 3) , C 3 = EXP. איזו מבין הטענות שלהלן היא הטענה החזקה ביותר אשר ידוע שהיא נכונה? (שימו לב להבדל בין הכלה להכלה ממש ⊂ ).

    • 2024 Semester A Moed AQ 13Transcribed1
    • 2024 Semester A Moed BQ 13Transcribed1
    Source pages (2)
    The page the question was read from — 2024 Semester A Moed A · p. 112024 Semester A Moed A · p. 11The page the question was read from — 2024 Semester A Moed B · p. 62024 Semester A Moed B · p. 6
    Time, space, and classesLessons 2, 3, 18
  14. 2 sittingsClosed questions2023–2024Computed match

    תהאנה A ו- B שפות כך ש- A L B. מה המסקנה היודעה נכונה:

    • 2024 Semester A Moed AQ 14Transcribed1
    • 2023 Semester B Moed AQ 14Transcribed1
    Source pages (2)
    The page the question was read from — 2024 Semester A Moed A · p. 112024 Semester A Moed A · p. 11The page the question was read from — 2023 Semester B Moed A · p. 132023 Semester B Moed A · p. 13
    Time, space, and classesNP, verifiers, and nondeterminismLessons 2, 3, 4, 5, 18
  15. 2 sittingsClosed questions2024Computed match

    ראינו בהרצאה רדוקציה מ- 3-SAT ל- Subset Sum. בהוכחת נכונות הרדוקציה התאמנו בין השמה שמספקת לנוסחה שבקלט לבין מספרים בפלט שסכומם הוא הסכום הנדרש. נניח שהקלט לרדוקציה הוא הנוסחה (x1 x2) (x1 x3) ונסתכל על ההשמה המספקת שנותנ…

    • 2024 Semester A Moed AQ 8Transcribed1
    • 2024 Semester A Moed BQ 8Transcribed1
    Source pages (2)
    The page the question was read from — 2024 Semester A Moed A · p. 72024 Semester A Moed A · p. 7The page the question was read from — 2024 Semester A Moed B · p. 42024 Semester A Moed B · p. 4
    NP, verifiers, and nondeterminismReductions and Cook–LevinLessons 4, 5, 6, 7
  16. 2 sittingsClosed questions2024Computed match

    נתונות הטענות הבאות? i. אם MAX-IS NP או P = NP. ii. אם IS P אם ורק אם MAX-IS P. iii. אם IS NP אם ורק אם MAX-IS NP. תזכורת: MAX-IS היא שפת הזוגות <G,k> של גרף ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k ואין בו קבוצה ב…

    • 2024 Semester A Moed AQ 12Transcribed1
    • 2024 Semester A Moed BQ 12Transcribed1
    Source pages (2)
    The page the question was read from — 2024 Semester A Moed A · p. 112024 Semester A Moed A · p. 11The page the question was read from — 2024 Semester A Moed B · p. 62024 Semester A Moed B · p. 6
    NP, verifiers, and nondeterminismNP-complete problemsLessons 4, 5, 8
  17. 2 sittingsOpen questions2021–2023Computed match

    3. נגדיר את בעיית המקסימיזציהC כלהלן. קלט: נוסחה בוליאנית 𝜑 מצורת2CNF שבכל הסגר שלה מופיעים שני משתנים שונים (בחיוב או בשלילה). מטרה: למצוא השמה אשר מספקת במובן NAE (Not All Equal )מספר מירבי של הסגרים בנוסחה 𝜑 . קבעו…

    • 2023 Semester A Moed AQ 3Text layer
    • 2021 Semester A Moed AQ 3Text layer
    Time, space, and classesNP, verifiers, and nondeterminismApproximation algorithmsLogspace and NLLessons 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 15, 16, 17, 18, 20
  18. 2 sittingsClosed questions2022–2023Computed match

    5. תהא C1 מחלקת השפותA ⊆ Σ∗ עבורן קיימים פולינום𝑝 ומכונת טיורינג דטרמיניסטיתM עם זמן ריצה פולינומיאלי כך שלכל 𝑥 ∈ Σ∗ מתקיים • אם 𝑥 ∈ A אז Pr𝑟[M(𝑥, 𝑟) = T] = 1, • ואם 𝑥 ∉ A אז Pr𝑟[M(𝑥, 𝑟) = T] < 2−𝑝(|𝑥|), כאשר…

    • 2023 Semester A Moed BQ 8Text layer
    • 2022 Semester A Moed AQ 5Text layer
    Turing machines and modelsTime, space, and classesNP, verifiers, and nondeterminismRandomization and probabilityLessons 1, 2, 3, 4, 5, 6, 7, 10, 12, 13, 14, 18
  19. 2 sittingsOpen questions2023Computed match

    1. קבעו האם הטענה שלהלן נכונה, אינה נכונה, אושקולה לשאלה פתוחה. הוכיחו קביעתכם. אין להשתמש בטענות או בתרגילים מהקורס מבלי להוכיח אותם. טענה: לכל שתי שפות A ∈ P , B ∈ coRP, מתקיים A ∪ B ∈ coRP. הטענה נכונה / אינה נכונה /…

    • 2023 Semester A Moed AQ 1Text layer
    • 2023 Semester A Moed BQ 1Text layer
    NP, verifiers, and nondeterminismRandomization and probabilityLessons 4, 5, 6, 7, 12, 13, 14
  20. 2 sittingsClosed questions2023Computed match

    3. נתונות שלוש מחלקות סיבוכיות .D1 = ⋃ DTime(2(𝑛𝑐)) 𝑐≥1 , D2 = ⋃ DTime(2(𝑐𝑛)) 𝑐≥1 , D3 = ⋃ DTime(𝑐(2𝑛)) 𝑐≥1 איזו מהטענות שלהלן נכונה (שימו לב: הסימון ⊊ מציין "הכלה ממש א. D1 = D2 = D3 ב. D1 = D2 ⊊ D3 ג. D1 ⊊ D2…

    • 2023 Semester A Moed AQ 3Text layer
    • 2023 Semester A Moed BQ 4Text layer
    Time, space, and classesHierarchy theorems and diagonalizationLessons 1, 2, 3, 10, 18
  21. 2 sittingsOpen questions2020Computed match

    3. תהאsuperNP מחלקת השפות A ⊆ Σ∗ עבורן קיימת מכונת טיורינג (דטרמיניסטית) M עם זמן ריצה פולינומיאלי כך שלכל 𝑥 ∈ Σ∗ מתקיים𝑥 ∈ A ⟺ ∃𝑤 ∈ 0,1∗. M(𝑥, 𝑤) = True. א. במה שונה הגדרת המחלקה superNP מהגדרת המחלקה NP (המבוססת ע…

    • 2020 Semester B Moed AQ 3Text layer
    • 2020 Semester B Special sittingQ 3Text layer
    Turing machines and modelsTime, space, and classesNP, verifiers, and nondeterminismLessons 1, 2, 3, 4, 5, 6, 7, 10, 18
  22. 2 sittingsOpen questions2020Computed match

    2. עבור שפהA נגדיר את בעיית ההכרעה Odd-A כלהלן קלט: מספר טבעי 𝑘 (בייצוג בינאריואוסף מחרוזות 𝑥1, 𝑥2, … , 𝑥𝑘. שאלה: האם מספר המחרוזות 𝑥𝑖 (1 ≤ 𝑖 ≤ 𝑘) שמקיימות𝑥𝑖 ∈ A הואאי-זוגי? קבעו האם הטענה שלהלן נכונה, אינה נכ…

    • 2020 Semester B Moed BQ 2Text layer
    • 2020 Semester B Special sittingQ 2Text layer
    Logspace and NLLessons 14, 15, 16, 17, 18, 20
  23. 2 sittingsClosed questions2020Computed match

    3. נגדיר את בעיית ההכרעהA שלהלן קלט: ייצוג ⟨M⟩ של מכונת טיורינגM עםא"ב עבודה Σ = 0,1,2,3, B. שאלה האם M מקבלת את ⟨M⟩ וגם𝑠𝑝𝑎𝑐𝑒M(⟨M⟩) ≤ |⟨M⟩|3 ? איזו מבין מחלקות הסיבוכיות שלהלן היא הקטנה ביותרביחס להכלה אליה ידוע שהש…

    • 2020 Semester B Moed BQ 2form 011/022/033/044Text layer
    • 2020 Semester B Special sittingQ 3Text layer
    Turing machines and modelsTime, space, and classesNP, verifiers, and nondeterminismReductions and Cook–LevinApproximation algorithmsLessons 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 18
What this map does not know

92 questions are counted here and shown nowhere: their readings — OCR or full-page — are not good enough to stand as text. They count toward the sitting totals, the topic split, and the anatomy, and are never used to claim that two questions are the same question.

Sittings are keyed by (year, semester, moed) because the exam filenames are not reliable. Clean-map text is displayed as-is; PDF text-layer readings are displayed with a caveat; OCR readings are counted and never displayed.

  • 2022 Semester B Moed A: the sitting is counted, but none of its questions were read well enough to show.
  • 2022 Semester B Moed B: the sitting is counted, but none of its questions were read well enough to show.
  • 2022 Semester A Moed B: the sitting is counted, but none of its questions were read well enough to show.
  • 2021 Semester B Moed A: the sitting is counted, but none of its questions were read well enough to show.
  • 2021 Semester B Moed B: the sitting is counted, but none of its questions were read well enough to show.
  • 2021 Semester A Moed B: the sitting is counted, but none of its questions were read well enough to show.
  • 2025 Summer semester Moed B: 7 of 10 questions are readable.
  • 2025 Semester B Moed A: 3 of 10 questions are readable.
  • 2024 Summer semester Moed A: 7 of 8 questions are readable.
  • 2024 Summer semester Moed B: 6 of 7 questions are readable.
  • 2024 Semester B Moed A: 3 of 11 questions are readable.
  • 2023 Summer semester Moed A: 6 of 7 questions are readable.
  • 2018 Semester B Moed B: 3 of 7 questions are readable.