3-CNF SAT (3 CNF Satisfiability)

In this video, we describe the 3-CNF SAT or the 3 CNF Satisfiability problem. We first explain conjunctive normal form and then discuss the 3-CNF SAT problem.

If you want to obtain a certification and a Algorithms Foundations badge from the State University of New York Binghamton based on the videos in this channel, please visit the link. For obtaining the certification, you will need to pass a multiple choice final exam based on these videos. The course also contains self-assessment quizzes to help you prepare for the finals and for obtaining the certificate.

This channel is part of CSEdu4All, an educational initiative that aims to make computer science education accessible to all! We believe that everyone has the right to good education, and geographical and political boundaries should not be a barrier to obtaining knowledge and information. We hope that you will join and support us in this endeavor!

---------
Help us spread computer science knowledge to everyone around the world!

Please support the channel and CSEdu4All by hitting "LIKE" and the "SUBSCRIBE" button. Your support encourages us to create more accessible computer science educational content.

---------
Find more interesting courses and videos in our website

---------
Find and Connect with us on Social Media:

[ohmpatel]

Dude the narration as well as the content is top notch ... Helped me out a lot .. Keep making vids you'll be big in no time!

[uberkarthik]

for extra credit points, couldve explained why the first part of the 3 cnf sat problem's statement was irrelevant in the example you provided. When you have an OR between x1 and its complement, it doesnt matter what the rest of the statement says in your example.

[hulk]

Sir how I show that unrestricted formulas can be converted into
restricted forms, and solution for both is the same

[anywaysjess]

I REALLY HOPE YOU ARE ACTIVE TO ANSWER THIS QUESTION
if we have a 3-CNF problem with only three terms instead of 4..(x1, x2, and x3) would I be able to assign x1 = 1, x2 = 1, x3 = 0 and check?

[amaldaagi]

give me an approximate satisfiability problem algorithm and thank you

[mohamedb]

I have a serious question: let's say all the litterals are independent, meaning if you have say X in one clause there will not be ¬X in another clause. in that case the solutions are trivial. and the number of those solutions is (2^3 - 1)^n were n is the number of clauses. now let's suppose we have dependent litterals like in your example. the trick is to set an nxor gate between all x and their respective ¬x, if the return is 1 it means x = ¬x and that solution is removed from the pool of all possible solutions. what you're left with in the end are true solutions. I believe if done correctly this can solve 3sat in linear time. I can already picture the custom made circuit for it. With that said I believe this algorithm is too simple, so if it works somebody would've done it by now, I guess my question is: what's u algorithm?