Understanding P vs NP: Formal Definition & Complexity

Let’s take a deeper look at the complexity class P, and decision problems.

Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Justin Chen, Elaine Chang, Zachary Greenberg, Alex Egan

Twitter: https://twitter.com/UBehavior

—

P vs NP Playlist: https://www.youtube.com/playlist?list=PLlwsleWT767dnN25K_QgvdKkovK_t4K6-
Decision vs Search: https://cseweb.ucsd.edu/~mihir/cse200/decision-search.pdf
The Complexity of Decision versus Search: https://cseweb.ucsd.edu/~mihir/papers/compip.pdf
P (Wiki): https://en.wikipedia.org/wiki/P_(complexity)
Decision Problem (Wiki): https://en.wikipedia.org/wiki/Decision_problem
Reduction (Wiki): https://en.wikipedia.org/wiki/Reduction_(complexity)
Function Problem (Wiki): https://en.wikipedia.org/wiki/Function_problem
Triangle Number (Wiki): https://en.wikipedia.org/wiki/Triangular_number