Description

In this video, Cara Weber introduces basic complexity categories for computing problems: P (those for which an algorithm can be written that finds a solution in polynomial time), NP-hard (those for which an algorithm can verify, but not produce, a solution in polynomial time; only an algorithm running on a non-deterministic Turing machine could produce a solution in polynomial time), and NP-complete. She also explains one NP-hard problem (the Vertex Cover Problem), and one approach to its solution (via a linear relaxation of an integer program).

Team Members
  • Cara Weber

Learn more about our fullstack JavaScript curriculum

Learn More