1
$\begingroup$

TLDR; Looking for Explanation of Cook-Levin theorem palatable to CS first years who are theory averse

I'm a prof. teaching first year algorithms+programming and want to give my students a taste of deeper CS theory.

In the very last week of class, I want to cover (in two lectures) the key idea behind Turing Machines NP-completeness, and NP ?= P.

I'd also love to somehow weave in Cook-Levin.

They won't have covered formal languages, so I plan to avoid them where possible. I will introduce SAT, and could talk about the number of variables in a tableau. We covered big-O and correctness proofs earlier in semester.

I'm also not a theoretician, so figuring out the minimal possible explanation that still contains meat is a bit tricky!

I'd love a) thoughts on how best to do this or b) an explanation that provides the key intuitions.

$\endgroup$
3
  • 2
    $\begingroup$ "Explanation of Cook-Levin theorem palatable to CS first years who are theory averse": how about "don't do it"? Just give them some standard examples (like shortest simple path, clique, etc.), say that the cleverest people in the world couldn't find better than exponential-time algorithms, say that there is a lot of such problems, and they are reducible to each other. The main takeaway for the people who won't go deeper is "there is a chance that you might encounter in practice a problem from category don't waste time trying to solve it efficiently, and try to check if it's such a problem" $\endgroup$
    – Dmitry
    Mar 29, 2023 at 23:18
  • 1
    $\begingroup$ (And mention approximation algorithms, e.g. simple approximations for TSP, and heuristics, e.g. local search) $\endgroup$
    – Dmitry
    Mar 29, 2023 at 23:22
  • $\begingroup$ I appreciate it's a little crazy... just trying to give them the flavour! But I agree with much of what you said. $\endgroup$
    – shaananc
    Mar 30, 2023 at 20:57

2 Answers 2

1
$\begingroup$

I anticipate that the Cook-Levin theorem and its proof will be too much for CS first-years. I do not recommend that you try to teach that.

Instead, I recommend that you show them something awesome that is appropriate for their level of development and understanding. Maybe show them two lectures on machine learning (e.g., via nearest neighbors), or two lectures on how some data structure or algorithm is applied in practice, or something else awesome. To get ideas for awesome things you can show them, I recommend taking a look at introductory courses at a few top universities and see what they do.

$\endgroup$
1
$\begingroup$

If you will introduce SAT then you could use a SAT solver to do Soduku.

$\endgroup$
2
  • 1
    $\begingroup$ SAT of course is essential for the Cook-Levin Theorem. If the full extend of that result is too much to grasp, then using a more familiar problem and transforming it into logical formulas is a good suggestion. $\endgroup$ Mar 31, 2023 at 22:08
  • $\begingroup$ When I translated Soduku into Propositional Logic, I was impressed that PL is more expressive than I thought. $\endgroup$ Apr 1, 2023 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.