# Explanation of Cook-Levin Suitable for First Years

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.

• "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" Mar 29, 2023 at 23:18
• (And mention approximation algorithms, e.g. simple approximations for TSP, and heuristics, e.g. local search) Mar 29, 2023 at 23:22
• I appreciate it's a little crazy... just trying to give them the flavour! But I agree with much of what you said. Mar 30, 2023 at 20:57