10 open questions. Closed-book — one double-sided A4 handwritten cheatsheet allowed. No calculator. Assume P ≠ NP and NP ≠ EXP. Karp reductions denoted ≤_P. Irrelevant information costs points.

Three archetypes with fixed templates that repeat identically on every exam. Nailing P1 is the pass/fail line.

Supporting skills. Construction is the broadest — covers Q1, Q2, Q3, Q5, Q6.

Lower-weight but still appears every exam.

Same format as the real exam (45 pts, 10 questions). Solutions are collapsible — try each question first, then check.

Save for final calibration after drilling archetypes + mock exams.

Must include:

• Decidability table (A/E/EQ for DFA/CFG/TM — decidable, TR, co-TR)
• Formal definitions: DFA 5-tuple, NFA 5-tuple, PDA 6-tuple, TM 7-tuple, CFG 4-tuple
• Pumping lemma statement
• NP verifier template
• CNF conversion steps (START, DEL, UNIT, TERM, BIN)
• Complement logic: TR + co-TR = decidable
• Reduction direction rules
• Known NPC problems + standard instances (3SAT, VC, CLIQUE, HAMP)

🟡 Draft + HTML done, not handwritten