Clyep

4 episodes, about 17 min 1 view across the series

Topics: Software and data foundations Code: abhydesai/p-vs-np-code

P vs NP Explained

Created by Abhyuday DesaiUpdated , episode 4

What P, NP, NP-hard and NP-complete mean, how reductions carry hardness between problems, and what to do when your problem is NP-complete.

Start with episode 1

About this series

Four short videos. Solving versus checking, and the open question. What a reduction is and how it carries hardness. What NP-hard and NP-complete actually name. Then the practical response: exact search, structure, approximation, and mature solvers.

Part oneThe classes

  1. 01

    Solving Versus Checking: What P and NP Mean

    Finding a subset that adds up is a search. Checking one you are handed is one pass. That asymmetry is what P and NP name.

    5:21 1 view Published
    Watch
  2. 02

    What a Reduction Is: How Hardness Passes Between Problems

    A reduction converts an instance of one problem into an instance of another, in polynomial time, keeping the answer. Follow the direction and hardness passes with it.

    2:53 0 views Published
    Watch
  3. 03

    NP-Hard and NP-Complete: The Problems Everything in NP Reduces To

    A problem every problem in NP reduces to is NP-hard; one that is also in NP is NP-complete. One fast algorithm for any of them would settle P versus NP.

    3:50 0 views Published
    Watch

Part twoThe practical response

  1. 04

    Your Problem Is NP-Complete. Now What?

    NP-complete is not hopeless. Four responses, with a dynamic program that answers subset sum for thirty numbers in an instant, and why that does not contradict the theory.

    4:38 0 views Updated , v2
    Watch