8. NP-Hard and NP-Complete Problems
Вставка
- Опубліковано 5 чер 2024
- P vs NP
Satisfiability
Reduction
NP-Hard vs NP-Complete
P=NP
PATREON : www.patreon.com/bePatron?u=20...
CORRECTION: Ignore Spelling Mistakes
Courses on Udemy
================
Java Programming
www.udemy.com/course/java-se-...
Data Structures using C and C++
www.udemy.com/course/datastru...
C++ Programming
www.udemy.com/course/cpp-deep...
10:15 when we don't know how things are working, we call it magic. Once we know how it works, we call it technique. Well said sir, well said.
😎😎😎😎😎😎
The moment I heard that, I stopped the video I liked it and I continued to watch. Thanks sir
I've never heard another instructor drop such badass quote, another reason why Abdul is the best!
There goes my harry potter excitement.
It's a common quote wdym
Whenever I am frustrated with my college CS professors and the way they explain topics I type "Abdul Bari" on youtube and never get disappointed! Thank you! You are a great teacher and person for doing this!
So do I LOL
This teacher is more interested in making the subject accessible than merely showing he is clever. Thank you Abdul.
Same here ❤
"watch this video only when you have time, don't watch this in a hurry"
*Proceeds to watch 2 hours before exam*
Absolute Mad Lad!
Exact same thought! 😂😂🤣🤣
I can relate to this xD
I have my exams after 4 hours
watching this 6hrs before my final lol
"watch this video only when you have time, don't watch this in a hurry"
me: reduce playback speed from 2x to 1.75x
Same 😆
lmao
thought i was the only one...XD
Why is this so relatable!
Same
Your teaching is a gift to college students. May you have the best of health and hope you make more lectures. Thank you, Sir!
He fat tho
I truly feel the same❤
السلام عليكم
Those 30 mins are worth than anything else out there.. Thanks for making life of algorithms a lot easier... You will be remembered professor ✌
Don't watch it in hurry, Me : who's watching it half an hour before exam 😂
Same bro😂
Samee us bro
It's f**ked me up in mid exam ,I don't studied ........2more hrs for my sem exam
When I attended the class to understand this topic it seemed like MAGIC, after watching this video it turned into LOGIC. Thanks a ton.
Absolutely great teacher, I'm an undergrad at MIT and I really appreciated this as an explanation to our design and analysis of algorithms class.
Glad it was helpful!
Bro wtf! Now I conclude brands don't matter.😆 No offence tho.
@@jay-rathod-01 hahahah
P vs NP 12:00
Satisfiability 14:45
Reduction 21:20
NP-Hard vs NP-Complete
P=NP
Thanks 👍
Tq
Cooks theorem
mann tq
thank you
Imagine your child, your grand child, any kid from the whole lineage going to Computer science . The link to this video is a treasure map for them.
Great video indeed ! Thank you for all your effort, dedication and passion. You are making a difference at a global level.
"But I guarantee that I ll make this topic easy !!! "
You did that sir ❤️❤️❤️❤️❤️❤️❤️
Everyone will get interest in study if this type of teaching will be there in every class then students will study with curiosity and the classes will not be bunked by the students. Thank you so much sir. Love the explanation!
Somesh Gupta maybe we can give the students the choice to take classes from any teacher they want.
That's A Yes!
Somesh Gupta
u R right....
Totally agreed
Totally Agree!
One of the best lecturer I have listened to! He delivers the concepts effectively and not taking more than polynomial time! Keep up the good work Sir!
i feel so sad about those got graduated 4 years ago without knowing what exactly these things are.may god bless this man to live longer and teach us more and more and more
the most beautiful moment in my life is watching your lectures in my laptop holding book and pen in my hand,feeling ahaaaaaaaaaaaaaaa.
😁
DEAR SIR,
Generally i dont write comments,but for this i have to...U r not better U r Best...
BEST REGARD FROM ME..DEAR SIR...
A FORMAL THANKES CAN'T SHARE THE FEELING OF MY HEART SIR.....
TEACHER LIKE YOU SIR,CAN CHANGE THE FUTURE OF INDIAN EDUCATION....
HOPE U SEE IT
Hats off to you sir, thanks for helping people like me.. May God bless you :)
This video proves that you are a great teacher sir and that too in constant time!
I HAVE NEVER EVEN PAYED ATTENTION IN A CLASS FOR 30 MINS . THIS DUDE MADE ME WATCH THE WHOLE THING. LEGEND.
I believe any difficult subject becomes boring or non-understandable to someone if the teacher fails to explain it in the way you did. It just increased my potential to think of new discoveries.
I really hope that teachers like you are discovered by us very soon because just like NP, gems like you are already there in our environment, we just need to discover them!
No comments... It's Amazing,., this is one of the toughest topics in my Algorithm course.,U made it simple ... Now One comment is not enough to describe how easy it is . love your lectures. keep doing more videos. Thank you sir..
You are the most amazing CS professor honestly. Your ability to explain such hard concepts and make them so understandable is a gift. I thank you to the bottom of my heart. Was so frustrated with my theory of computation class and because I didn't understand anything my professor was saying in this topic, a professor with multiple researches and PHDs. God bless you and your family. You re an awesome teacher!
God Bless you.
Absolutely the best teacher, straightforward and without EGO.
One of the finest explanations I've come across UA-cam. There are other videos with better jazz (animations/funny quips etc), but none take their time in explaining a complex computer science concept so patiently. Well done! Thank you so much for your time...
the first ever time, i have figured out them. A BIG THANK TO YOU SIR.
Sir. You earned respect. You know how a student can learn. They way you explain everything is too good and understandable. I wish all students get a chance to come across prof. like you. Thank you sir.
I am really becoming perfect in algorithms and data structures because of watching these videos from best lecture Abul Bari sir.
I am grateful to you for support and explanation.
man this is so much better than my lecturer, he assumes we are geniuses and i don't even know what he is muttering in class, the way he explained is just too technical
Many many thanks sir..yes we want all topics should be discussed in as much easy way as possible sir..our all respect and love for you sir..
I attend my algorithms lecture for 3 hours a week and don't understand anything, then I watch your videos and understand everything. That's magic
I have tried so many time to understand p, np etc but everytime the professors tried to scare us as if I had to be a PhD to even begin to understand what it all means. You cleared it up in a second. I am not even a CS guy, I just like learning about random things. Thanks a lot.
One moment I was watching a poker tournament and a moment later I'm into this youtube rabbit hole and it has brought me here. Incredible. This stuff is fascinating, and I don't understand a thing about it.
What a video!! Awesome. I was trying to understand these things for a long time. 30 mins and I am wiser than the guy I was 30 mins before.
I have gone through many books for this topic... But i never felt easy then... You are the only person who can convert NP topics to P topics👏👏thank you sir
I am an undergrad at IIT. Mindblowing explanation Abdul bari sir !. I have completed 2 courses made by you about to finish 3rd !!. You will be remembered FOREVER, You actually increased my confidence exponentially in programming!
Thanks Ishank,
May God Bless you with Happy and Peaceful life.
Sir.U are just simple awesome.I haven't read this course thoroughly through out my semester.I had watched your videos 2 days before the exam and I'm able to attempt the question paper incredibly good.Thank u so much sir🙏. Hat's off for to your teaching.Great explaination.
WOW, I have learned so much, I wish every teacher was like you. I love CS, and you just made me love it more. Thank you !
MAY GOD BLESS YOU WITH A LONG LIFE , ABDUL SIR .....!!!
Hell of an explanation. I was trying to get my head around in P, NP, Np-Hard, and Np-Complete problems for the last one day with no progress. This video made it all clear. Great job. Became a fan of this channel...
Sir, you convert all the topics that I feel are NP-Hard into P. ❤❤😊
Sir, excellent video. U r a great inspiration to us in delivering NP hard and complete to our students. Hats off.
Start from 11:10 if you have already watched and want to revise
@harshitdongre4982 would you believe if i tell you i am watching this in my office right now.
I watched 2 lectures amounting to 2.5 hours from my Algorithms class and I got much less out of that - than I did from this video. 30 minutes is very worth it. Thank you so much.
This is the most straightforward, easy explanation I have ever heard on this topic. The way you explained it has intrigued me to learn more about this topic and not just dread it for exams. Thank you for this.
Sir your videos length may be long but content and knowledge are far bigger.. Great sir
Great explanation I have ever seen
!
You are really a great teacher in this planet
.
Million of love, respect and Salam for you sir !
From Dhaka, Bangladesh!
I have watched so many videos and classes to understand the P vs NP maze. Finally, you explained everything very clearly with just a 30 minutes video. I am really grateful. Thank you.
Don't underestimate this teacher due to his indian accent, he makes PERFECT sense !
Thank you for making this subject accessible to the likes of us - we are very grateful that you would freely provide such quality material.
Understanding the concept of NP-Hard and NP-complete problems itself, was NP-Hard, which thanks to +Abdul Bari has become NP-Complete
att kamal hasann
Just Wow
The way you explained Satisfiability and related it to 0/1 knapsack was blown up my mind. You just made complex terms very easy. I learn much in your classes rather than university. Thank you sir.
I've never seen such an amazing yet simple yet descriptive tutorial for NP Complete and NP Hard. Kudos to you sir!!
You're a savior for CS enthusiasts.
the problems which are solved in less number of time gave us the whole support and much better understanding for solving these logcal problems.Resprct sir, Salute You for giving such abrilliant and nice explaination about these problems in such a nice way 🙏
Hello Sir, truely appreciated the clarity of explanation, and the content, It was awesome easy to understand one difficult concept. I will follow all other of your
Lectures
Hats off to you Sir! You yourself proved what you claimed! Till I heard you about this topic through this video, the whole concept was just unknown oh no, unimaginable to understand I mean Non-Deterministic and now after listening to you it has become too simple that now we started playing with polynomial time requirements and deterministic. Simply great Sir. Awesome, amazing, ... falling short of words to thank you Sir for all the services you are rendering to the society by making people to believe that they can do wonders which they never had even dreamt that they could do so. I mean converting NP to P!!!!
I got your course, watched nearly every video for my algorithms class & passed. Now I am doing another course where we actually looked at reductions and P & NP. I never understood even the slightest thing in class. This is amazing!
It helped me a lot.was trying to understand from college.Im clearly able to understand now after 7 years.Thanks a lot sir.
U r the best teacher sir.I have also taken ur course of DSA of Udemy.U r genius sir.U can teach the toughest of concept with absolute simplicity.keep on making such videos sir it is the most useful for students
It's fascinating how humans are proving the existence of better solutions that we may find for these problems in the near future. Seems like a huge and significant step. Understood in one go. God gifted teacher.
I'm shaking my head in disbelief... why aren't you my professor for EVERYTHING? This is how someone explains something! Wow. Bless you, bless you, bless you. Thanks a ton.
Usually people with this kind of knowledge don't have time to be on UA-cam, I thank you very much for your clear explanation and hopefully, I will see more and more videos of you with time. I have a small request though, if you would please put some references at the end of each video so that people who are interested in a subject can read more or cite a reference if needed.. Also, is it possible that you explain some metaheuristic methods in the future? it would be great.. thanks a lot
Sir the concept regarding P and NP class was never so much clear before I watched your video. Please make video about decidability, undecidability and halting problem of turning machine, Recursive and recursively enumerable languages. Thank you sir.
Extremely Helpful Video Sir... And yes I am watching this with enough time, I still have One day left before exam...
Hello Abdul. I am from Brazil. Your video is simply the most didactic and clear on UA-cam on this subject. Thanks!
Really u r the same as sarvepally radhakrishna, we can't saw the first teacher. ... But I proude to u seeing.. super sir
Namaste Sir, Thank you from USA. me and my frds are learning a lot from your video than our lecture in class. Thank you!
Whenever I lost all hope about learning a topic, this person makes me believe that I can, and his videos are very helpful. Thank you sir. 🙏
No one has ever explained this concept in a better way than you. Amazing work! Thanks a ton!
Superb explaination sir thanks for making video...
Your explanation is very nice.
Please explain why SATISFIABILITY problem is having non-determinism.
Satisfiability is non-deterministic because it is part of a class of algorithms that cannot be solved quickly but can be verified/checked quickly. It means we hope to one day "fill-in the blanks" to make it polynomial and deterministic.
If somebody gave you a boolean satisfiability problem and asked you to solve it, it would take you a very long time to solve it depending on how many variables were involved.
But if somebody gave you a boolean satisfiability problem AND gave you the answer to the problem, well, then you could quickly check that the given solution is indeed correct.
When I say it would take you a very long time I mean it would take you longer than polynomial time. It would be exponential time. When I say it would take a very short amount of time, or you could do so quickly, I mean it would take you polynomial time or less.
I hope this helps.
@@TastyLaserCakes Good explanation, cheers!
I have just completed M.Sc(Mathematics with Application in Computer Science).
I am preparing for a job interview.Your classes are helpful for me Thanks,Sir
Don't watch if you're in hurry got me on my knees 😂😂😂😂 how did you read my mind sir? good luck on your exams
Sir thank you for sparing your time to explain these algorithms with a good explanation.
Can you please upload a video on cook's theorem
Thankyou very much sir, me and all of my friends watch your videos. To be honest I have my exam tomorrow morning😅
Your style of teaching is really amazing, I already had the notes of this topic with me as my teacher provided them, I even tried to read them but it all seemed so confusing and out of place that i ended up quitting in between. But now i feel really confident for my exam.
Thanks and regards☺
This is the best video on Computational Complexity across UA-cam. Well Detailed and Well Researched . Kudos to you Sir
Thanks alot. I understood this topic after 17 years of completion of my masters. Wish all teachers are like you then no one will find algorithms topic difficult.
Hats of you.
Your expalanation makes even the hardest topic easy to understand. Can't thank you enough :)
I was just going to increase the playback speed to 2X and then you said if you are in a hurry then don't watch 😂😂, so i watched it in normal speed and understood everything , thank you guru ji 💙💙
5 days left for exam....I have never seen anyone explain Algorithm so easily....Loads of love and respect, Sir
First bench student spotted before 5 days😮
This is a very well structured and friendly overview of the groups. The fact that you utilized the binary tree as means of illustrating Turing reduction is very clean also.
Thank you so much~!
He saved one Korean's life
this class better not be the reason i don't graduate 😭😭
Your words are diamond. I'm a CS students and had hear this a lot of times but never with this approach. Super valued!
Perfect class . Time flies during lectures like these . Hats off !!!
No word to say sir, just you are amazing ...i love you sir.
The ppl who made comments here are abt to take his or her final within 24 hours..
this is the only place I understood the difference between NP, NP-hard and NP-complete... Thanks
awesome ... very well explained , i was trying to clear my concepts of Np hard and Np complete since many days, i have gone through so many videos.. but sir u made it really easy for us thanks alot
To all who have been here before me, to all who have watched these videos one day before their algorithm exams, know that the torch is being passed on and the tradition is being kept alive. I hope to make the indians who make these tutorials proud, like you have done when it was your turn to tackle this course. Wish me luck, and I wish all who come after me luck as well. Let's do this!
God Bless you sir!
You are a savior to student like me, i read entire chapter in textbook about NP-Complete vs NP-hard, but couldn't understand what was the topic about
but i watched this video, and everything is clear and concise
Thank You So Much!
I am 100% sure i will get a perfect score on my final exam now
:)
I have completed my university study without having such a clear understanding of NP hard and NP complete probems. Thank for this explanation. Well done!
I had seen multiple videos for the P and NP problem but believe me, I was unable to understand a single word. I randomly find his video and when he said if u r in hurry don't watch it, I knew there is something in it and now after half an hour I know what is P, NP, NP-hard, Complete. Sir, u deserve a standing ovation (y). Outstanding. Thank u so much for teaching.
Teaching skills - God level. ❤️🙏
Hello, I would like to send you a giant THANK YOU. Your videos helped me pass my algorithms class and allowed me to graduate college! You have an amazing skill for explaining complicated concepts in a clear and concise way. I am so grateful my dad showed me your UA-cam channel. Thank you again!
Great job!
Thanks for sharing Good news.
I wish you all the success and happiness. 👍😊
Wasting lots of amount on clgs...... Our lectures are learning from u and explaining in class, that too not in clear.... But u r videos are dam good. We need more teachers like u too sustain in engineering ❣️
The hero none of us deserve.
Omg god should bless with good health u r blessing for students😍
i dont have words to thank you for this video. i hv exam this week and i was totally confused about this topic and now the thing is i a gona write this ans and diagram in my exam for sure. you are more than amazing sir.one request from me plz upload more videos on this analysis and design as well as data structure advance topic, i am asking about learning programming and coding.
sir, you have already uploaded such a nice video on imp topics, u could choose yourself for any topic left. i just want to understand in a coding way cz your way of teaching is beautiful. topics like like structure , linked list, heap etc.thanks again for your reply
What else one needs if he is blessed with a teacher like you! I am so much glad to learn from you. Your explanations are incredibly crystal clear. You deserve great respect sir!!!!! I really want to meet you someday sir. Please tell the way I can reach out to you. Thankyou so much for your support. God bless you!
I didn't get this concept when my teacher taught me also. You are excellent.
Your explanation is a treasure.