Рет қаралды 28,465
Here we give a polynomial-time reduction from 3SAT to Vertex Cover, and show that VC is in NP, thereby showing that it is NP-complete.
If you like this content, please consider subscribing to my channel: / @easytheory
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.