R8. NP-Complete Problems

Рет қаралды 122,772

8 жыл бұрын

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Amartya Shankha Biswas
In this recitation, problems related to NP-Completeness are discussed.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

Пікірлер: 82

@karansvnit 6 жыл бұрын

4:34 Hamiltonian cycle -> Hamiltonian Path 13:00 Clique -> Independent Set

@whocares995 4 жыл бұрын

karan patel thanks

@MNMLSTN 3 жыл бұрын

My dude walked in straight from the afterparty. Respect!

@smoothGuaperator 2 жыл бұрын

thought I was the only one that noticed

@MS-qh3iz Жыл бұрын

how did you know?

@luisribeiro2239 6 жыл бұрын

Great explanation! The first lecture that really makes sense... Very well explained in details. Very smart guy! Thank you, Amartya! Keep on!

@hassanalamri2665 6 жыл бұрын

I have a professor that I pearly understand what he was talking about for like four classes with total 12 hours. However, all that I can say is thank you so much. I am really glad to have knowledge from a person like you.

@ahmedrekik4534 7 жыл бұрын

After showing several videos about NP Problems and reductions (especially in graph theory), it's the first time that I could find such an intuitive lecture and understand these problem. Thank you Amartya!!

@Chatbot121 2 жыл бұрын

He went fast, but still did well

@unknown6656 5 жыл бұрын

04:30 HamiltonianCycle ==> HamiltonianPath 13:00 K-CLIQUE ==> K-INDSET 21:50 K-CLIQUE ==> MAX2SAT

@MagnifiqueRarity 7 жыл бұрын

Great video! Very comprehensible!

@BELLAROSE21212 Ай бұрын

**NP-complete decision problem:** Given a value for X, determine whether there exist integers A and B such that: * A - B = X * B = ln(A) This problem is NP-complete because it is a special case of the subset sum problem, which is a known NP-complete problem. **Reduction from subset sum problem:** Given a set of integers S and a target integer T, the subset sum problem is to determine whether there exists a subset of S that sums to T. We can reduce the subset sum problem to the NP-complete decision problem as follows: 1. Let S = {a1, a2, ..., an} be the set of integers and T be the target integer. 2. Create a new integer X = T + 1. 3. Determine whether there exist integers A and B such that: ``` * A - B = X * B = ln(A) ``` If there exist integers A and B that satisfy these conditions, then there exists a subset of S that sums to T. This is because we can set A = T + 1 + sum(subset) and B = ln(A), where subset is the subset of S that sums to T. Conversely, if there do not exist integers A and B that satisfy these conditions, then there does not exist a subset of S that sums to T. Therefore, the NP-complete decision problem is NP-complete. In this case, the decision problem of finding the values of A and B that satisfy the equation A - B = 4 and B = ln(A), where A and B are integers, is NP-complete. However, there do not exist any integers that satisfy this equation. Therefore, we can conclude that P does not equal NP. This is a very important result in computer science, and it has many implications for the field. For example, it means that there are some problems that cannot be solved efficiently by any computer, no matter how powerful.

@alexba1771 7 жыл бұрын

Nice video presented by a clever guy. I really like the video!

@sumanmondal001 6 жыл бұрын

Its awesome to see KZfaq is recommending mother's lecture when son is delivering lecture... :D

@heisenberg_737 3 жыл бұрын

Same thing happened with me XD

@l441828872 5 жыл бұрын

What a brilliant young lecturer!

@at1with0 5 жыл бұрын

Given the completeness theorem what problem in proof theory about syntax does the SAT problem translate to?

@study7691 4 жыл бұрын

Thank you, now everything is clear.

@hj2931 Жыл бұрын

Great recitation! The later the video the more tricky, creative and fun 🤣🤣

@sukhadakulkarni1511 2 жыл бұрын

Great explanation! Thank you!

@minasmz2006 3 жыл бұрын

well explained! Thank you!

@droliaonfire 5 жыл бұрын

we have to show number of clauses to be more than k then what's the need of E' and k as only V number of clauses should be sufficient, isn't it?

@ADNANNAZIR2012 3 жыл бұрын

5:40 how? Aren't we supposed to not repeat any vertex in Hamaltonion cycle?

@x0cx102 4 жыл бұрын

kind of wanted to see him talk about turan's theorem

@lechenwang8641 5 жыл бұрын

why do we have to create a dummy variable z???

@Shiegao 8 жыл бұрын

Is there another lesson on this topic

@nehag5990 4 жыл бұрын

Great Explanation!

@therealaverma 4 жыл бұрын

Amazing video overall, really appreciate it. One note of feedback from me: I got confused for a while at 31:47 because I thought you were writing out subtractions. Once I rewinded a bit to listen to how you defined V' , then the 3 clauses became clear to me.

@xuhuiwang5682 8 жыл бұрын

hope more examples could come up....

@deepikarajani3201 6 жыл бұрын

great explanation

@sheikhmujahed8133 4 жыл бұрын

12:51, His style, juz bring it on.

@bartekbinda1114 4 жыл бұрын

Since 2sat is in P, can anyone explain the difference between max2sat and 2 sat?

@harrywang6792 3 жыл бұрын

2 sat is whether if there is an assignment to the literals so ALL clauses are satisfied; max2sat is whether there is an assignment to the literals so at least K clauses are satisfied. So s sat is a special case of max2sat, where k = number of clauses. If that helps.

@FaNTaCoLa90 7 жыл бұрын

There is a minor error in the "Clique - Independent set" reduction example. An edge is missing in the transformed graph.

@rayzhang336 7 жыл бұрын

What is the definition of Z? what's its role?

@therealaverma 4 жыл бұрын

I think it's an arbitrary addition to the literals for the purpose of isolating certain vertices

@Rififi50 3 жыл бұрын

It’s an additional variable to prevent a zero solution: Without z you can set x_i = 0 for all i and obtain the maximum, since all (not x_i or not x_j) would be 1. Adding constraints with z prevents this. Note, however, that z is still a variable and thus is either 1 or 0, still potentially allowing a zero solution. Adding a constraint on both z and not z prevents the zero solution. For example: No z: x_i = 0 for all i -> (not x_i or not x_j) = 1 for all (i, j) in c(E) -> All constraints are fullfilled, i.e. the maximal solution Only constraint with z: x_i = 0 for all i, z = 1 -> (not x_i or not x_j) = 1 for all (i, j) in c(E) and (x_i or z) = 1 for all i in V -> All constraints are fullfilled, i.e. maximal solution Constraints on both: x_i = 0 for all i, z = 1 -> (not x_i or not x_j) = 1 for all (i, j) in c(E) and (x_i or z) = 1 [always fulfilled!] and (x_i or not z) = 0 for all i in V -> Potentially not maximal! Changing one x_k to 1 already increases the number of fulfilled constraint by 1, namely: (x_k or not z) = 1

@AndrewLvovsky 4 жыл бұрын

I thought my player was stuck at double playback speed... thanks for the lecture Amartya!

@levi23244 4 жыл бұрын

Same here :)

@bharathmagpie2034 6 жыл бұрын

Thanks a lot bud :)

@ILORVYt 6 жыл бұрын

Make sense?

@tylertyler82 6 жыл бұрын

@TheLouisandKyleShow 3 жыл бұрын

very helpful

@raghul1208 2 жыл бұрын

excellent

@harrywang6792 3 жыл бұрын

23:12

@badpoochi 7 жыл бұрын

INAUDIBLE: @5:39 And, that problem is NP-Hard, so you can't solve it in polynomial time

@badpoochi 7 жыл бұрын

INAUDIBLE: @6:03 ==> You can just start anywhere and visit all the vertices and stop

@ilovejingle Жыл бұрын

make sense!!!!

@zechi7790 6 жыл бұрын

What the hell of that "Nintendo games or something" xDD

@samiere 6 жыл бұрын

See lecture 16, they showed how to reduce 3SAT to a nintendo problem

@sarahli2933 4 жыл бұрын

He is so cute!

@bechirjamousi6696 3 жыл бұрын

It really does not make sense!

@Chiavaccio 2 жыл бұрын

👏👏

@kutilkol 4 жыл бұрын

"..you can't solve it polynomial then...", true if P != NP 5:38

@karthikthelord 2 жыл бұрын

KZfaq why am i seeing this

@slybuster 8 жыл бұрын

Take your coat off--stay awhile.

@donman256 6 жыл бұрын

Maybe he is cold.

@OLGACT2011 6 жыл бұрын

Man's not hot

@Xakanis 6 жыл бұрын

Style is everything

@droliaonfire 5 жыл бұрын

this guy explains well...doesn't actually matter whether he wears a coat or not

@nanoha94 7 жыл бұрын

he's cute ^^

@SHASHANKRUSTAGII 6 жыл бұрын

he's INDIAN

@In7enseCA 5 жыл бұрын

@@SHASHANKRUSTAGII wow a cute indian xd

@thangible 3 жыл бұрын

definitely cute

@vas_show 4 күн бұрын

THATS WHAT I THOUGHT

@user-tk2jy8xr8b 5 жыл бұрын

So many "so" and "dash" instead of "prime". But everything else is fine

@WowPlusWow 4 жыл бұрын

Isn't he hot in that jacket?

@RANVEERSINGH-ly5ee 5 жыл бұрын

As far as I know 2SAT is in P and Max Clique is NP-Complete. Sorry to say but I did not understand this lecture at all.

@victos-vertex 5 жыл бұрын

Because you missed the word "max" in front of 2SAT. The example wasn't about 2SAT, which is indeed in P, it was about max2SAT. Max2SAT is NP complete and this is what was shown in this lecture.

@smoothGuaperator 2 жыл бұрын

@@victos-vertex damn you came with some attitude

@Gandobilis Жыл бұрын

👽

@bharteshnandkar3367 6 жыл бұрын

lets just say this is connected to this guy..haha

@harsherharsh 6 жыл бұрын

this is too difficult to comprehend.

@deopen 4 жыл бұрын

Not helpful at all ! waste 20 minutes of my time + 2 min for this comment. He can use little example for some reduction e.g. max2sat reduction from k-clique, that was so unclear to me.

@study7691 4 жыл бұрын

A potato would do better than this cameraman! Show the board!!! The board!!!!