8.1 NP-Hard Graph Problem - Clique Decision Problem

Рет қаралды 571,449

6 жыл бұрын

NP-Hard Graph Problem - Clique Decision Problem
CDP is proved as NP-Hard
PATREON : www.patreon.com/bePatron?u=20...
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...

Пікірлер: 286

@dhankumari7290 4 жыл бұрын

When we don't know how the things are working we call it is magic Once we know how it is working it becomes technique / Logic ~ Abdul Bari

@studyhelpandtipskhiyabarre1518 Жыл бұрын

that's awesome, which video did he say that in

@god_gaming178 Жыл бұрын

@@studyhelpandtipskhiyabarre1518 he said that on np-hard and np-complete video

@veenapal7849 Жыл бұрын

9 🎉😅

@aadiamitringay3032 3 ай бұрын

its not that deep lil bro

@JoshuaBharathi-rz7ry 3 ай бұрын

@@aadiamitringay3032 Bet you finally felt like a man after saying that

@ritubanerjee5061 4 жыл бұрын

Sir I was planning to leave this topic for my exam, but after watching your video, I have decided otherwise. Lots of respect to you Sir! Your lectures are simply outstanding!!!

@roshinroy5129 2 жыл бұрын

Same for me man

@amritrajawat3083 Жыл бұрын

@@roshinroy5129 sama for me

@taaaaaaay 2 жыл бұрын

This man is singlehandedly saving my CS degree

@swatisinghmar702 Жыл бұрын

so true

@anshumansamanta5632 24 күн бұрын

Please also watch the lectures of Dr.Khaleel Khan sir , the God of O.S and Algorithms .

@ankitdubey9256 4 жыл бұрын

The first time I am writing a review on any channel, but really I love to take lectures from you. The way you tell any topic is just amazing. Thank You Abdul sir.

@INNOVATIVEAPPROACH 6 жыл бұрын

sir , i have ssen this vedios only once and its awesome and very helpful as I understand it in one go . Your way to descibe the nitty gritty of CDP is very well .!!! I cannot resist to write a thanks to you .

@akshayganji7412 2 жыл бұрын

I feel these series are the best on Algorithms. I have binge watched most of your videos and they are so easy and straightforward to understand. Even my Professor with a PhD can't explain this well and confuses things beyond imagination. Kudos to you Sir! And thank you very much for this.

@atharvakaranje6538 6 жыл бұрын

Would love to see more lectures on such problems! Nicely explained!

@chrisogonas 4 жыл бұрын

That was very clear, sir. I don't know how I've never bumped into your great lectures. Thanks

@JC-cu2ym 3 жыл бұрын

Thankyou sir! I finally understood SAT reduction to Clique problem in one go. You are brilliant at explaining!

@alexwenstrup5202 3 жыл бұрын

Finding good information and videos on NP is so hard, thank you so much for this helpful, quality content!

@YehiaAbdelmohsen Жыл бұрын

Understanding NP-Hard is NP-Hard

@dheerajkafaltia8474 5 жыл бұрын

Amazing, would not have been able to complete it reading in books a day before exam Helped a lot :-) Thank you sir

@rakeshkumaranjani4988 4 жыл бұрын

your way of teaching is very simple and you sir deliver a high quality education on this platform. Thank you sir You are great doing for students of india and all over globe also

@anupamroy1455 6 жыл бұрын

Sir your videos are very nice your explanations are crystal clear please try to upload more videos on data structures and algorithm with implementation in c it will be really helpful

@frozenjellyfish6114 2 жыл бұрын

I watched so many videos abt cliques, this is the only one explained cliques and np prob clearly. Thank you so much

@MrDarkStar974 4 жыл бұрын

Thanks a lot sir ! I'm a french student of computer science and i had to demonstrate the NP-Completeness of CDP. Without your help it would have been a lot more complicated. Especially since there's hardly any help in French for this demonstration.

@sabrinanastasi5809 7 ай бұрын

Thank you one million times for this video. It's like no words to express how much you have the gift of breaking down complex topics into smaller easy ways to explain. Thank you.

@mantistoboggan537 6 жыл бұрын

This was a really outstanding explanation. Thanks!

@siddhibudhale4352 5 жыл бұрын

Sir, your method of teaching is really really accurate and nice. Got to understand by watching just once. Thank you very much.

@priyeshkumar4814 4 жыл бұрын

Sir your videos are very clean, straight to the point and easy to understand. Thank you ;)

@vaishnaviakki8363 5 жыл бұрын

Sir you are a super hero for me! Thank you so much,these videos helped a lot for my exams Keep making videos like these😊🙌🏻

@cuteDali 4 жыл бұрын

you are great teacher. From yesterday, I tried to solution my homework but I couldn't. Now I understand. Thank you very very much

@DevSecNetLabs 2 жыл бұрын

One and only saviour before the semester exam. A lot of thanks to sir on behalf of all the students' community. ❤

@anweshamitra4016 6 жыл бұрын

till now the best vedios i have seen sir...keep doing and keep helping us like this

@pauljones9150 2 жыл бұрын

Best algorithm prof on youtube. I feel more confident after watching your videos

@rahulroy5206 3 жыл бұрын

May God bless u sir, stay Happy, stay healthy, we want more videos from u to make life a bit easier❤️

@sounakbanik3087 5 жыл бұрын

Your videos are a saviour for us students. A must watch for exam and gate preparations

@supriyacse-bg7978 Жыл бұрын

Your lectures are simply outstanding!!

@vipingautam9852 5 жыл бұрын

Sir you are amazing, i just want to touch your feet and show my respect to you :) whenever i get stuck i just search for you videos and i never get disappointed.

@Foodicouple 6 жыл бұрын

thnq so mch sir you made it look so easy thnx a lot

@florencenightingale9532 5 жыл бұрын

Sir ,your explanation is soo clear.it really helping us a lot...

@lmachado73 4 жыл бұрын

Excellent! Thank you for the explanation! Best regards from Brazil :)

@chinmaydas4053 6 жыл бұрын

Nicely discussed a difficult problem..

@gudiravisankar5164 6 жыл бұрын

Very good explanation on NP Hard and NP Complete and what it is, i got some idea into mind of what it is now.

@melvyntie8391 5 жыл бұрын

THANK YOU SO MUCHHH, YOU REALLY SAVE MEEEEE

@sohamchakrabarti2713 5 жыл бұрын

He literally made my college education free. Damn!

@xfactor2462 6 жыл бұрын

I myself am a teacher . Your videos are awesome. I always see your videos while teaching.

@nivedhahari4908 5 жыл бұрын

A very helpful video...excellent explanation..thanks so much sir

@sharvarithombre129 5 жыл бұрын

Thank you so much for the video. Clearly explained

@sampadkar19 Ай бұрын

This is an excellent lecture on this topic. Not many KZfaq videos cover this subject. Thank you, Sir.

@dawidmachalica2286 5 жыл бұрын

Very well explained. Thank you!

@sahith2547 2 жыл бұрын

Sir.....!!! Great explanation......you blew our mind with the proofs....🥳

@mab2278 6 жыл бұрын

Clear and just made simple. Thanks

@kirua_h 3 жыл бұрын

Thank you sir ! Your videos really helped a lot !

@vishalsharma-bd3uj 3 жыл бұрын

Dear sir i have learn lots from you and i think you are the best teacher on that platform to explain all the hard concept easily. Now i am requesting to you please make a video on proof of np complete problem also.

@ananyasinha9282 6 жыл бұрын

THANK YOU SO MUCH!! Very clear, to the point explanation. Happy to find a good teacher on KZfaq :)

@mohammadyousef2812 5 жыл бұрын

Thank you very much for your clear explanation.

@dparikh1000 8 ай бұрын

Abdul is the man. He is keeping me interested in CS and discrete mathematics.

@Klausx007 Жыл бұрын

Tommorow is my DAA mid exams and you are saving me from getting failed. Hahaha. 💜

@GanesanMNJRF-CSE 3 жыл бұрын

Very clear explanation, hats off to you sir!

@mouniikaperam2394 6 жыл бұрын

Ur videos are helpful.. nice explain everypoint uu explain in detail..

@VegitoUltraI 3 жыл бұрын

His easy approach made me write this comment.. This guy is awesome❤❤

@harsimranjeetsingh2693 4 жыл бұрын

you're the reason imma pass my algorithms final

@babithap4738 Жыл бұрын

Thank you sir for making me to understand difference between P,NP,NP Hard and NP Complete problems with such an easiness

@ramancheema20 5 жыл бұрын

Sir ,Your videos are too good .Sir could you pls provide a video on countability and decidability as well

@rishabhkumar2264 6 жыл бұрын

thanks u making such nice tutorials.Can u make video on how to prove a problem is np complete or not??

@mubashirmufti5941 Жыл бұрын

You have made this difficult topic easy to understand, Thanks

@muthierry1 2 жыл бұрын

You are the best one Sir .. Great Professor ever ..

@rajsharma-bd3sl 3 ай бұрын

I am Stanford University student and I am learning from this legend . Hatsoff to you !!

@richadhiman585 5 жыл бұрын

Vedio is very beautifully explained.. Thanks for the vedio.

@ArtinJ 2 ай бұрын

This man is an international treasure. Protect him at all costs!

@bhagyalaxmidhatrika2713 5 жыл бұрын

Sir very nicely explanation sir......more videos on data structures in cpp sir

@ottodvalishvili7601 6 жыл бұрын

Great Explanation.THanks a lot

@ridwanatolagbe3279 11 ай бұрын

The video really disambiguated the concepts. Thank you very much sir for efforts.

@priya28881 Жыл бұрын

SIR , I JUST WANT TO BOW DOWN TO YOU. EVERYTHING IS CRYSTAL CLEAR TO ME WHEN YOU TEACH. SIMPLY OUTSTANDING!!!!!!

@abdul_bari Жыл бұрын

God Bless You, Dear.

@FootyPick 6 жыл бұрын

Sir what is vertex cover problem? Are Clique and Vertex cover problem same?

@hjain1011 2 жыл бұрын

Sir you had made excellent videos. Thank you very much 😊. Can you further make a video about reduction of np complete problems. With some 5 reduction , that tree starting from satifiability to some famous problems.

@joyone6031 Жыл бұрын

Thank you Abdul Bari, you save my final exam!!!

@markriad3910 5 жыл бұрын

nice explanation , just a small questions : based on what u build the satisfiability formula ? is there guidelines to built the needed formula so we can have the correct relation to our corresponding problem ?

@vibecatcher4416 5 жыл бұрын

Thanku sir . . i hope that , i can defenetily write this ,in my answer sheet , tomorrow ,, 😘

@srinunaidu6581 5 жыл бұрын

Sir your videos are easy to understand....

@michaeleluz9445 Жыл бұрын

No words can describe my gratitude to you

@meerasolgama7324 5 жыл бұрын

Hello sir! Your teaching skill is very best👍👍👍👍👌👌👍👍

@ankan979 5 жыл бұрын

Please make a video asap on proving vertex cover as np hard. No other youtuber is as good as you in making things understand to be honest.

@yourSportss 4 жыл бұрын

Very very nice sir i am very happy today i learnt after long effort because i am not a student of maths

@asaf4isr 4 жыл бұрын

Great Video, the only thing that bothers me, the reduction done from 2-SAT, but, 2-SAT in P, i know the same construction you showed will work from 3 sat to clique neither. please explain.

@kartikeyagupta651 4 жыл бұрын

2-SAT problem is in P then how can it be used to prove clique as NP hard?

@skittles6486 4 жыл бұрын

Exactly. I also wrote it in comment.

@panepomodoro 3 жыл бұрын

Very nice, Sir Bari. Thanks a lot.

@c.danielpremkumar8495 6 жыл бұрын

How does one decide the number of variables in each clause and number of clauses ? Also, within each clause, which variable(s) to be with a "Bar" (NOT) or normal.

@jonahbartz1033 5 жыл бұрын

@@abdul_bari If you had a 4 clauses with 5 variables in each clause then would the clique size still be 4(size of clauses)?

@aronquemarr7434 4 жыл бұрын

@@jonahbartz1033 Yes, it would.

@himeshmishra5186 6 жыл бұрын

I watched the MIT video on NP for 1hr::25min but didn't get a word but sir the way you have taught us it in 2 videos is commendable. This Indian Education System a peace of shit where University hires the incapable professor and make this Research topic like hell in which teacher like you sir saves us. Thanks a ton sir... Keep sharing the knowledge sir.

@RAHUL-uc3cy 6 жыл бұрын

Great lecture

@BTS-kw5ec 6 жыл бұрын

Nice explanation 👌👌👌

@renjitharejikumar1619 5 жыл бұрын

Thank u Sir...helped me a lot

@AKSHAT150 4 жыл бұрын

Amazing Explanation Sir!

@v.k.miruthula8559 6 ай бұрын

Excellent teaching sir. I am forever grateful to you.

@adityakhera8470 2 жыл бұрын

salute to you sir thank you so much!! best professor sir!

@tesfayea.naramo6540 4 жыл бұрын

thank you for your clear explanation but i need to know what if we are given 1000 clique is thin in Np? and how can i prove it ?

@Shortvideo-ru3sm 3 жыл бұрын

Sir, you solved my long pending problem

@zishanahmad8248 2 ай бұрын

best explanation ABDUL BARI Sir . Thank you

@lijunxian3862 2 жыл бұрын

Thank you for helping my exam!

@aliyafathima9634 4 жыл бұрын

Sir if possible try to post a session on "Node Cover Decision Problem"

@shree2710 6 жыл бұрын

Please also discuss NCDP and CNDP!!

@gbw4908 5 жыл бұрын

Could you make more videos about np problems? These are very helpful!

@SintuKumar-dg2qz 5 жыл бұрын

@HAI-Tech 5 жыл бұрын

Sir can you please suggest me some book for Algorithm course. I;m MSCS student. Thank you

@sid-jj6mq 2 ай бұрын

Sir, In future videos kindly move aside once at the end of video so that the whole board is visible. Its difficult to go back and front again to write the part of the board that u r cover for the entire video. Great video sir. Thankyou.

@yogeshrichoudhari4039 2 жыл бұрын

Thanks a lot Sir. Very well explained

@imalishahzadk Жыл бұрын

could not understand this video... previous video was much helpful. by the way, all other videos were much helpful. thank you.

@AryanGNU 5 жыл бұрын

This man is incarnation of God #Respect

@leedai4492 2 жыл бұрын

sir you teaches much better than my ivy school teacher

@samiamuhammad8140 5 жыл бұрын

Please can you explain proof by reduction independent set and vertex cover?

@Hanible 5 жыл бұрын

You're a good teacher sir, only one question: where does the rules of drawing the graph from the SAT formula come from?

@williammize3248 4 жыл бұрын

The edges are representing the AND condition between clauses of the SAT formula that can evaluate to true. You can't draw edges between nodes of the same clause because those have an OR condition between them. You can't draw edges between nodes that are negations of one another, because that condition will never be true. You cannot have x AND ~x evaluate to true.