The Satisfiability Problem, and SAT is in NP

Here we introduce the SAT problem, which consists of a boolean formula (with variables and operations AND, OR, and NOT). We also show that SAT is in NP via certificates.

▶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.

[EasyTheory]

Thanks to my supporters Yuri (Youtube) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.

[arcdia]

Satisfiability is a hard problem. I worked on this problem with my wife for years.

[sameersutar-]

Watching this just before my theory of computation exam. Thanks for the video brother :)

[joesilvester]

your videos are very easy to understandable sir..Thank you.. ..keep continue sir

[Mrsalonangel]

Thank you for explaining! needed just a quick explaining about 3 sat and more

[ayushijmusic]

Thanks for the explanation. What might be the time complexity to verify the solution >?

[manavkumbhare]

You are the best teacher in the world. I want to meet you please replay

[joesilvester]

Outline, in pseudocode, an exact algorithm for the problem. This should guarantee a solution if one exists. how to find this sir

[timurtimak]

Is it true that the hardness of the hashing algorithms: SHA-2, SHA-3 relies on the SAT problem?

[amirhosseinomidi]

nice dude but i dont get why SAT is so hard?