The Satisfiability Problem, and SAT is in NP
Вставка
- Опубліковано 25 сер 2024
- 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.
Thanks to my supporters Yuri (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
Satisfiability is a hard problem. I worked on this problem with my wife for years.
This is amazing
Watching this just before my theory of computation exam. Thanks for the video brother :)
your videos are very easy to understandable sir..Thank you.. ..keep continue sir
Thanks!
Thank you for explaining! needed just a quick explaining about 3 sat and more
Easily Understood , thanks
You are the best teacher in the world. I want to meet you please replay
replay .. dude 💀
Thanks for the explanation. What might be the time complexity to verify the solution >?
NP, unless we crack quantum computing, then it will be P
The guy above me is doubly wrong.
1- Verifying a solution is in P.
2- No, we don't know if SAT (or any other NP-Complete problem) will be efficiently solvable with Quantum Computers. It is thought that they won't be.
when should we backtrack?
Outline, in pseudocode, an exact algorithm for the problem. This should guarantee a solution if one exists. how to find this sir
Eventually I will do this video.
Is it true that the hardness of the hashing algorithms: SHA-2, SHA-3 relies on the SAT problem?
Not SAT directly but, as explained in the video, it relies on P != NP. For it P = NP, then hashing becomes "easily solvable", which would be very bad for our tech security.
very
nice dude but i dont get why SAT is so hard?
The thing is - it might not even be hard! It's just that every technique ever tried so far yields an exponential time solution, and there are heuristics to suggest no "fast" algorithm exists for SAT.
From the way you wrote the comment, I feel like you might be misinterpreting the meaning of "hard". By "hard", in this context, we don't mean "hard to understand" or "hard to find an answer to, as a human." It more or less means that " Given n inputs for a problem, the computer will take exponential time to solve it (basically O(2^n) or such time-complexity)". Think about it this way, if we are given x1, x2 and x3, as our sat problems variables(AKA inputs(n) = 3), and the problem itself is, lets say (x1 or (-x2)) and (x2 or (-x3)). Then the generic way to solve it would be to test each and every possibility of x1, x2 and x3. As each of these inputs can be either True or False, that means two possibilities for each input. and as there are three inputs, the number of possibilities become 2*2*2 = 2^3. Same way, if there were 10 inputs, we would get the 2^10 possibilities (We can optimize a bit depending on the exact problem, but the rate of growth of time, relative to the no. of inputs will stay the same). This exponential increase in possibilities( more possibilities means more time taken by the computer ) with respect to the number of inputs, makes it so, that by something like a 100 inputs, we will have around 10^30 something possibilities. This means that even high powered computers will take extremely long time to compute the answer( I am talking years here), in the worst case scenario. That is the basic meaning of "hard" in this given context, and that is the reason why SAT is considered an NP(Non-Polynomial, as in time complexity can't be represented in polynomial) problem. Now, the reason why it is speculated that it might not even be NP, is because, we don't have any clear evidence that there isn't an algorithm to solve SAT, that runs in polynomial time. Hope it cleared up your doubt, and if you find any flaw in my explanation, feel free to reply. (As I replied one year late, I guess your doubt was already solved, but if not, hope this helps).
@@sayantanshaw4608 dude your explanation is op.
@@EasyTheoryThanks for your excellent video. How do I publicizes my findings in a Math/Computer Journals and what would be the right Math/Computer Journals. I would be really appreciate if you show me the path for publicizing my findings.
this guy looks like elon musk