00:02 NP-completeness: an entire field in one lecture 02:37 NP problems can be solved using nondeterministic models by making guesses 09:10 Nondeterministic algorithm can find a satisfying assignment for a formula 11:26 NP is a powerful model that allows for easy verification and guessing 18:29 NP-complete problems are not in P unless P equals NP 20:56 Reductions help prove that a problem is NP-hard 25:51 The second part is about reductions 27:44 Reduction is a powerful technique to prove NP-hardness of a problem. 32:00 The problem of reaching the end of a level in Super Mario Bros is NP-hard. 34:02 The level in the video represents the existence of choices for variables. 38:03 Traversing through clauses to win the level 39:59 To traverse all the clauses, they must all be true 43:55 Valid traversals in the Mario game 45:40 Super Mario Brothers is NP-hard. 50:47 Converting formula into equivalent three dimensional matching input 53:15 Building a variable gadget with two solutions: true and false 57:50 Using garbage collection as a gadget to cover uncovered points in NP-completeness 1:00:14 Subset Sum problem can be reduced from Three Dimensional Matching. 1:04:43 Converting triples into a number in base b 1:06:51 Choosing a set of numbers that add up is the same as choosing a set of triples that covers all elements. 1:12:03 Partition is easier than Subset Sum 1:14:19 Partition is weakly NP-complete 1:19:33 Complexity: P, NP, NP-completeness, Reductions 1:21:49 4-partition is a strong NP-hard problem
He is really good, this lecture however I did not like the introduction of reduction on Super Mario Bros, I never played the game before, it felt like I had to learn 2 things at once, I understood the 3DM reduction a lot better.
I just wanna say that I had a complexity test today where I had to know what is NP-complete etc.... I didn't go to any of my class about this subject. And your course just made me understand this in an easy way than my class THANK YOU
This is so well done! I study in German and it's always difficult to switch learning in another language because you already know all the terminology in the first language you've learned it in. But this was brilliant, it explains everything I couldn't understand from my own professor, thank you MIT!
Language. What language do you speak? Mine is mathematics. What was EINSTEIN DOING IN A PATIENT OFFICE? YES (HEARE) IS YOUR JOB. HMMMM? IS THAT JOB TO SEE WHAT IS COMING THROUGH THE PATENT OFFICE. JUST WONDERING.
The following is just for my future reference: @1:05:33 Now in each disjoint set there are n elements and so total number of elements is N=3n. Now we allocate a N digit(location) array. We assign natural numbers to the elements... first n to elements in Z, next n to elements in Y and the last n to elements in X such that 0
Lots of persons are complaining about a so called communication lack of skills from the teacher. Please, don't get your lack of comprehension of the problem because of its inherent difficulty mixed up with Demaine's stand up skills
He handles that chalk like a boss. Old school. Throwback to the 1980s. I love it, LOL I didn't know anyone used blackboards anymore until I watched this.
Fantastically explained! Much better than my own university course; reductions are such a tricky topic to bend your mind around so I really appreciated this!
I believe the second statement in lecture @20:49 is incorrect. It should be the other way around: if A is in NP, then B is in NP, because reduction implies that for A->B, A is at most as difficult as B. Otherwise, we can always convert from A to B and then solve it. As a result, this shows that if A is in NP, then it will not be P, which implies B will be in NP as well. In the meantime, I do not believe the second state: "if B is in NP, then A is in NP" is correct because I can easily reduce a polynomial time algorithm to a NP problem such as MBM into MVC.
First of all, if we can reduce problem A to B, it means B is not easier than A. If as you said "If A is in NP", then we cannot say anything about B since B could be NP or NP-hard. Further, P is a subset of NP. if B is NP, then A could be P or NP. Therefore, it is still correct to say A is in NP. If B is P, then we know A must be P too. The whole point is that B is the upper bound of A. It is meaningless to say "if A is xxx, then B is xxx , since B can be anything harder than A. If we say "if B is xxx, then A is xxx", this is meaningful as we know the worst case complexity for A. This is what the professor wrote.
With sudoku grids there is centered orientation data so like a 4 in the middle of a nine by nine sudoku grid would equal 0000 or 0 and all the numbers on the outer and inner corners would equal 1111 or 15 in bigger than 16 by 16 grids the corners would equal 2222 or higher dights. from orientation data of differt numbers in the grid you can find where a faulty 2 state is and the 2 state falls to one state meaning when you radix the problem unkown states can be collapsed to a 1 or a 0 thanks to centered orientation. you can shuffle in some ways a suduku grid and position more density of known data towrads the center then go from the center outward.
There is a typo at 20:40-20:50, should be [ (A in NP ) --> (B in NP)] as reduction is saying B is at least as 'hard' as A is, this is the contrapositive of (B in P) --> (A in P).
Note that P is a subset of NP, not the complement of NP. Thus the contrapositive would be (A not in P) -> (B not in P), not what was claimed above. If we think of the difficulty graph illustrated by the presenter, then problem A reduces to problem B amounts to A is at or to the left of B. So (B in NP) -> (A in NP) is accurate.
First of all, if we can reduce problem A to B, it means B is not easier than A. If as you said "If A is in NP", then we cannot say anything about B since B could be NP or NP-hard. Further, P is a subset of NP. if B is NP, then A could be P or NP. Therefore, it is still correct to say A is in NP. If B is P, then we know A must be P too. The whole point is that B is the upper bound of A. It is meaningless to say "if A is xxx, then B is xxx , since B can be anything harder than A. If we say "if B is xxx, then A is xxx", this is meaningful as we know the worst case complexity for A. This is what the professor wrote.
@@TheOYENDRILA First of all, if we can reduce problem A to B, it means B is not easier than A. If as you said "If A is in NP", then we cannot say anything about B since B could be NP or NP-hard. Further, P is a subset of NP. if B is NP, then A could be P or NP. Therefore, it is still correct to say A is in NP. If B is P, then we know A must be P too. The whole point is that B is the upper bound of A. It is meaningless to say "if A is xxx, then B is xxx , since B can be anything harder than A. If we say "if B is xxx, then A is xxx", this is meaningful as we know the worst case complexity for A. This is what the professor wrote.
Why create the last crossover gadget instead of using pipes to move you where you need to be? Or was the spirit of the exercise to use the most basic implementation of Mario possible? Is the whole goomba/mushroom thing better? (Also, the final mushroom check can be a small tunnel of fire vines short enough for the hit invincibility to last, but full enough that small Mario can't pass.)
**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.
Q on proving NP-completeness: if X is NP-Complete it belongs to both NP and NP-hard I understand that you have to show that X belongs to both sets. But if you have a reference NP-complete problem like 3SAT wouldn't it suffice to show that 3SAT is reducible to X? Why do you need step 1?
because any problem can be reduced to a no-less-hard problem. So if we show 3SAT is reducible to X, we only should X is no-less-hard than 3SAT. This only means X is in NP-Hard. Step 1 is to show X is in NP.
This is where I had to hit pause, take a break and come back to it later. I need time to figure out just what exactly the problem is and by the time I have figured it out, the lecture will have gone on to many other things that I missed. I don't do too well with many abstract symbols.
The point is that P is a subset of NP. So if B is NP, A could be P or NP, and it is not sure. But it is always safe to say A is in NP, because if A is in P, it is also in NP.
As far as I understood. 1) If B is in P, then A is also in P : This is saying that if problem A can be converted to problem B in poly-time and if problem B can be solved in poly-time then it follows that you can also solve A in poly-time. 2) If B is in NP, then A is also in NP: This is saying that if problem A can be converted to problem B in poly-time and if problem B belongs to NP i.e. its solution can be verified in poly-time, then A must also belong to NP. This doesn't mean that A cannot be faster than NP. Problem A could belong to P while also belonging to NP, as P is in NP.
@@dailyfightvideos4269 If you have the time, go back and watch it again. The pause button is your friend. With material like this, you have to walk before you can run. But once you've figured out how to walk, you might surprise yourself with how fast you can run.
Wikipedia: For each variable xi, there is a "variable gadget" shaped like a wheel. It is made of overlapping triplets. The number of triplets is twice the number of occurrences of xi in the formula. There are exactly two ways to cover all the vertices in the gadget: one is to choose all even-indexed triplets, and one is to choose all odd-indexed triplets. These two ways correspond to setting xi to "true" or "false". The "true" selection leaves uncovered exactly one vertex in every odd-indexed triplet, and the "false" selection leaves uncovered exactly one vertex in every even-indexed triplet. For each clause xi u xj u xk, there is a "clause gadget" shaped like a rose. It is made of three overlapping triplets, one for each variable in the clause. It can be covered iff at least one of the nodes is left uncovered by the selection of the variable gadgets. Since it is possible that two or more nodes are left uncovered, we also need a "garbage collection gadget". It is shaped like a larger rose. It is made of several overlapping triplets, one for each vertex that can be left uncovered in the variable gadget. The number of such gadgets is determined so that they can be covered exactly if and only if there is a satisfying assignment.
I would have liked to see Tetris since the game is easy to understand but playing it to win is NP Complete. Would have liked to see that proof. Seems you can reduce the jigsaw problem to Tetris to prove it is NP Complete.
Just call a group of possibilities out of the possibilities in a sudoku cell, then there should be so many 1's per adjacent row column and subgrid. This way of encoding the problem should be enough to smash np complete problems in p time
"In my proposed solution, I introduce a novel computational paradigm that enables us to efficiently solve NP-complete problems in polynomial time. This paradigm revolutionizes the way we approach complex computations and leverages previously untapped connections between P and NP. Through extensive testing and analysis, I demonstrate that this new paradigm effectively solves a wide range of previously intractable problems. The proof involves constructing a transformation algorithm that efficiently converts any given NP problem into an equivalent P problem, providing compelling evidence for the equality between the two classes. The implications of this proposed breakthrough would be tremendous. Industries such as optimization, cryptography, and artificial intelligence would experience a significant leap forward. The ability to efficiently solve NP problems would enhance decision-making, accelerate scientific discoveries, and revolutionize various fields reliant on computation.
Most "reasonable people" believe in the Axiom of Choice, yet we know that's hardly "reasonable." The legal standard of "reasonable actor" applied to computational complexity theory wipes out constructivism in one burp. Thus 6.046J alienates arguably its greatest ally.
How does he conclude that rectangle packing is weakly NP-Hard? In general, I’m a little confused about how he’s concluding NP strength/if/how it’s transferred with reductions. It makes sense to me how he showed subset sum to be weakly NP-hard, and maybe why partition was also therefore weak (because it is reducible to finding a subset sum of t?). It would make sense to me that any time you can reduce a problem A to a weakly NP-Hard problem B, that you could conclude that A must not be strongly NP-Hard (and that if A is NP-hard it must be weakly so). However, with rectangle packing we only did the one way reduction from partition to it. This doesn’t by itself guarantee that rectangle packing is weakly NP-Hard, does it? That is reducing a weakly NP-Hard problem A to some other problem B doesn’t guarantee that B is also weakly NP hard, does it? Otherwise every NP-Complete problem would be weakly NP hard, because some weakly NP Hard problem reduces to it, and clearly some NP-Complete problems are strong NP-Hard. Now that I think back on it, an NP-Hard A -> weakly NP-Hard B reduction also doesn’t seem to imply that A is weakly NP-Hard, because any weakly NP-Hard problem being NP-Complete would imply all NP-Complete problems were weak, another contradiction. So how is he determining strength or weakness of these problems? Is it something I’m missing or just a detail he’s glossing over?
I have a question about the proof strategy for a problem being in NP. It's said you let a non deterministic turing machine guess the good answer and then verify it in polynomial time, completing the proof. But how do you know that there wasn't an actual polynomial deterministic algorithm to get those guesses? By that reasoning, everything in P is actually NP if we just let a machine guess the right answers. What am I missing?
If problem A can be converted to problem B(which is NP complete) in polynomial time then, what can we say about problem A? Is problem A, NP then? I think that nothing can be said about A. Can someone please confirm?
If problem A can be converted to problem B, then A is no harder than B. So if B is NP, then A must be at most NP (could be P but we don't know) if B is P, then A must be at most P which is P.
@@zichaohu9301 no mistake. If problem A can be converted to problem B, then A is no harder than B. So if B is NP, then A must be at most NP (could be P but we don't know) if B is P, then A must be at most P which is P.
It depends. If B is P, then most certainly A is P. If B is NP, then we can relax and say A is at most NP, even when A in truth is P, given P is a subset of NP (we can reduce P to NP). It gets tricky though when B is NP-complete. If B is NP-complete and A could be reduced to B, shouldn't that mean A is both NP and NP-hard and therefore, NP-complete? And isn't that why, in order to prove the completeness of A, we first ensure A is NP and then try to reduce a problem Z which is NP-complete to A (essentially declaring that A is either equal to or harder than Z, i.e. NP-hard)? Now, if B is NP-hard and one can reduce A to B, only here we cannot say what exactly A is, i.e., A could either be NP or NP-hard or both (NP-complete). Please correct me (with explanation) if I am wrong.
A nondeterministic machine would guess a true cover and check it in polynomial time. it checks that the problem is indeed an instance INST of 3D matching and it checks that the cover (the 3DM) covers XUYUZ both are done in polynomial time of the size of the input INST instance of the problem
Can someone please tell me when he says there is no polynomial time algorithm to solve 3 set problem, does he also mean polynomial time space or nothing about space?
Courses like this are vital for understanding the deeper ideas of algorithms. Knowing such things might rarely bring you an direct advantage but it's good to know for understanding 'everything'
I can't speak for the whole course, but the concepts of computational complexity (this lecture) are useful for determining how efficient an algorithm is, or even how difficult a problem is. Practical instances of these mathematics can be found in cryptography and cryptanalysis. The RSA crypto-system is based on integer factorization, a problem which is in NP and Co-NP. This gives people an idea of how difficult RSA is to "break". Cryptanalysis has a number of different methods of attack, which can be categorized by efficiency (how much time or space an algorithm uses) using P, NP, and so on. This gives us an idea of how useful a theoretical attack is.
It's really important to know how hard is to solve a problem. Knowing that a problem belongs to the class of NP-Hard for instance might mean that it takes "forever" to be solved for large inputs, so we need to prune the solution space some heuristics first for example. The guy doing the class is one of the smartest persons on earth but I usually don't like his teaching. See book "Introduction to the Theory of Computation" for a good coverage on these topics.
Impure Drunkard's Walk, It's extremely odd of you to pick an interesting and sophisticated pseudonym like PureChaos if you don't already know the answers to your question here. You very clearly don't live up to the good name your are discrediting.
No, Z*, that's wrong. You flunk. The specific material in this course will give anyone a bit of a handle on how long it will take to solve their problem. It will also save some people tens of millions of dollars by telling them in advance not to bother wasting their money. You really should not post to the Internet when you don't have a clue what you're talking about. * Not Z1rk31. What Z1rk31 posts is correct and intelligent. I see that Z has now removed their stupid post. Good.
Wait, so you are proving not that the game super mario is NP-hard but that you can construct NP-hard levels in mario? The fact that people have said Super Mario is NP-hard has always confused me.
It means you can't build a computer program guaranteed to find a way to the end of the Super Mario maze and win that level. At least that's what seems to be going on here. Can't build a robot to ace Super Mario Brothers, LOL
When we say Super mario is NP-hard, we are saying that it is harder or equally hard to every problem in NP (basically that every problem in NP reduces to Super mario). We already know that 3-SAT is NP-hard, so if we show that you can reduce 3-SAT to super mario bros, then Super mario bros is at least as hard as 3-SAT, meaning that Super mario is also NP-hard. So in the proof we constructed some gadgets so that we can map any instance of 3-SAT to some instance of Super mario bros. Since this is possible, we have that 3-SAT reduces to Super mario bros and thus Super mario bros is NP-hard. Tl;dr because we were able to reduce 3-SAT to Super mario bros. We know that Super mario bros is at least as hard as 3-SAT, if not harder, and so it too is NP-hard.
The definition of NP at 3.45 min. is wrong! You do not guess one out of polynomially many options, but out of an exponential number of options (say a SAT problem on k variables has 2^k possible assignments, not k^{O(1)}). The adjective polynomial describes the time complexity of the checking function, not the number of options. If one could choose out of polynomially many options, one could simply enumerate the options and check each of them in polynomial time... which implies P=NP.
The definition is not wrong. You have to take into regard, that it follows the idea of non-deterministic computing. Thus the computational steps may be at least growing exponentially in any amount of time O(1). Polynomially many options are then given and it's possible to guess an option which resolves to YES. The time needed would be 0(1), of course. If you were to enumerate those options and check all of them (in polynomial time, as you stated correctly), you would already have used non-deterministic computing and the overall effort would still be at least be k^{O(1)} for any given SAT(k).
See what you mean. But this is not what the guy says. He is talking about a "good guess which leads to a yes answer", which implies that a guess is a satisfying assignment for a set of variables. There are an exponential number of such guesses. In your interpretation he should have talked about about a set of guesses, one for each variable. I stick to my point ;-) But thanks for pointing this out to me. It explains why the confusion emerged....
This may clear things up: a non-deterministic Turing machine can solve a problem with an exponential number of options in polynomial time, and it can solve a problem with polynomial options in constant time. In his definition, of NP he's referring to the later case, where a deterministic machine would have to check through each of N^k possibilities, but an non-deterministic machine could guess which of the N^k possibilities is the right one. You can think of this process as occurring at each branching of an exponential problem, where there could be up to N^k branches to check. The non-deterministic machine knows which branch to take (and makes this choice N^k times moving down the tree), whereas the deterministic one has to check every branch.
The options in the SAT problem which we guess are whether each variable is true of false. Those are constant and so are polynomial. You first guess the first variable, then the second and so on.
should NP be the set of decision problem that can be solved in polynomial time with Non-deterministic machine, or, the set of decision problems whose "TRUE" instances can be solved in polynomial time with ND machine. if the former, how is it different from co-NP
If we have a problem A that is in NP and we reduce it to B then we know that B is NP. if we dont know if A is NP and we know that B is in NP are we sure that A is in NP?Could'nt be an algorithm that do not use this reduction but solves the A problem? is the second statement in ruclips.net/video/eHZifpgyH_4/видео.html correct?
A is at most in NP and no more harder. Of course A could be in P. But P is a subset of NP so his statement still holds. The whole point is that A cannot be harder than B, i.e. B is always on the r.h.s of A on the difficulty line he draw
I can't fully understand that @18:52, the professor stated that "X is NP-hard if every problem y ∈ NP reduces to X". Doesn't it mean that a problem(NP) would then reduce to a harder problem(NP-hard)? How should I interpret it? Thanks!
Reduction ... Time point ruclips.net/video/eHZifpgyH_4/видео.htmlm28s . Chalkboard writing .. then A element of P ... seems to disagree with the notes from the MIT site ... which is written A element of NP ... . Are the notes incorrect?
Could someone please help me understand what did he mean by, "Computer would guess an option from polynomially many options"? I am not able to think(and relate) of an example when an algorithm guesses while solving a decision-based problem. e.g. while determining a chess move. His next statement only adds to my confusion, "The guess is guaranteed to be a good one" :(
I don't know if this answer is too late, but: no computer can do this in real life! It's just a theoretical model, like if there were a computer that could always make the right choice in a decision based problem, it could do this in p time..
Super Mario Bros example was fun, but the 3DM explanation is really bad and doesn't make any sense, and he seems to be basing the rest of the reductions on that one. So 50 minutes pretty much wasted for me (plus the hour+ I used for rewatching the 3DM part again and again, and googling other explanations for it). Very much not recommended.
a question : you play lottory. chances 1: 14 Mil. for 6 out of 49 Numbers. What is the chances according to P vs. NP I hope, i hear from u guys & girls🍻
I have no idea what he’s talking about or what the subject even is. Sometimes I wish to know in a nutshell what this subject means and its purpose, while being in plain average IQ english and in one sentence. My brain is too ignorant and smol for this lol
To my understanding, 1. Most problem are very hard (NP-hard); 2. If you found that the solution to your problem can be used to solve some known NP-Complete problems, then you know your problem is NP-hard; 3. If you do solve your NP-hard problem efficiently (polynomial time), then you should examine it very carefully that it may bring you some awards.
The first ever video on NP-completeness where I started to understand at least something. MIT is the best. The lecturer is brilliant.
00:02 NP-completeness: an entire field in one lecture
02:37 NP problems can be solved using nondeterministic models by making guesses
09:10 Nondeterministic algorithm can find a satisfying assignment for a formula
11:26 NP is a powerful model that allows for easy verification and guessing
18:29 NP-complete problems are not in P unless P equals NP
20:56 Reductions help prove that a problem is NP-hard
25:51 The second part is about reductions
27:44 Reduction is a powerful technique to prove NP-hardness of a problem.
32:00 The problem of reaching the end of a level in Super Mario Bros is NP-hard.
34:02 The level in the video represents the existence of choices for variables.
38:03 Traversing through clauses to win the level
39:59 To traverse all the clauses, they must all be true
43:55 Valid traversals in the Mario game
45:40 Super Mario Brothers is NP-hard.
50:47 Converting formula into equivalent three dimensional matching input
53:15 Building a variable gadget with two solutions: true and false
57:50 Using garbage collection as a gadget to cover uncovered points in NP-completeness
1:00:14 Subset Sum problem can be reduced from Three Dimensional Matching.
1:04:43 Converting triples into a number in base b
1:06:51 Choosing a set of numbers that add up is the same as choosing a set of triples that covers all elements.
1:12:03 Partition is easier than Subset Sum
1:14:19 Partition is weakly NP-complete
1:19:33 Complexity: P, NP, NP-completeness, Reductions
1:21:49 4-partition is a strong NP-hard problem
If you're looking for reductions specifically he starts defining it at 15:25
I used to always think that good universities meant that it’s harder I now understand that it means they just teach the material way better
and therefore harder concepts are more digestible
He is really good, this lecture however I did not like the introduction of reduction on Super Mario Bros, I never played the game before, it felt like I had to learn 2 things at once, I understood the 3DM reduction a lot better.
His lectures are as brilliant as his shirts. Thank you for sharing!
I just wanna say that I had a complexity test today where I had to know what is NP-complete etc.... I didn't go to any of my class about this subject. And your course just made me understand this in an easy way than my class THANK YOU
This is so well done! I study in German and it's always difficult to switch learning in another language because you already know all the terminology in the first language you've learned it in. But this was brilliant, it explains everything I couldn't understand from my own professor, thank you MIT!
ethz ?
Language. What language do you speak? Mine is mathematics. What was EINSTEIN DOING IN A PATIENT OFFICE? YES (HEARE) IS YOUR JOB. HMMMM? IS THAT JOB TO SEE WHAT IS COMING THROUGH THE PATENT OFFICE. JUST WONDERING.
20:49 scared the hell out of me
lmaoooo
This Man Is A Genius. His Eyes tell me so. Looks like he has more to say than can be compiled.
Just a regular joe here...I'm glad we have professors like this man, teaching those who understand the course(s).
joe mama
What course is that?
So this is what freedom of information feels like
The following is just for my future reference:
@1:05:33 Now in each disjoint set there are n elements and so total number of elements is N=3n. Now we allocate a N digit(location) array. We assign natural numbers to the elements... first n to elements in Z, next n to elements in Y and the last n to elements in X such that 0
😀All the best
Dude's t-shirt collection is legendary.
Yes!!
Beautiful. Simply amazing. Thank you so much Prof Erik, you're a rockstar!
Erik Demaine strikes again
Expect takedown notice from nintendo
not until after my algorithms exam plz
Fair use.
Well? 2022
No idea wtf this comment is about, and six years later in 2023 it’s still up. So what are you on
they're notoriously known for takedown notices whenever their name mentioned. at least they used to.
Lots of persons are complaining about a so called communication lack of skills from the teacher.
Please, don't get your lack of comprehension of the problem because of its inherent difficulty mixed up with Demaine's stand up skills
This guy explains it really well for me and I consider myself a layman XD
He handles that chalk like a boss. Old school. Throwback to the 1980s. I love it, LOL
I didn't know anyone used blackboards anymore until I watched this.
Fantastically explained! Much better than my own university course; reductions are such a tricky topic to bend your mind around so I really appreciated this!
what an amazing lecture
This channel/video/professor/MITOpenCourseWare is a blessing to the world.
I believe the second statement in lecture @20:49 is incorrect. It should be the other way around: if A is in NP, then B is in NP, because reduction implies that for A->B, A is at most as difficult as B. Otherwise, we can always convert from A to B and then solve it. As a result, this shows that if A is in NP, then it will not be P, which implies B will be in NP as well. In the meantime, I do not believe the second state: "if B is in NP, then A is in NP" is correct because I can easily reduce a polynomial time algorithm to a NP problem such as MBM into MVC.
First of all, if we can reduce problem A to B, it means B is not easier than A. If as you said "If A is in NP", then we cannot say anything about B since B could be NP or NP-hard.
Further, P is a subset of NP. if B is NP, then A could be P or NP. Therefore, it is still correct to say A is in NP. If B is P, then we know A must be P too.
The whole point is that B is the upper bound of A. It is meaningless to say "if A is xxx, then B is xxx
, since B can be anything harder than A. If we say "if B is xxx, then A is xxx", this is meaningful as we know the worst case complexity for A. This is what the professor wrote.
48:00 alien gender was 3 at the time, now 72 for humans
With sudoku grids there is centered orientation data so like a 4 in the middle of a nine by nine sudoku grid would equal 0000 or 0 and all the numbers on the outer and inner corners would equal 1111 or 15 in bigger than 16 by 16 grids the corners would equal 2222 or higher dights. from orientation data of differt numbers in the grid you can find where a faulty 2 state is and the 2 state falls to one state meaning when you radix the problem unkown states can be collapsed to a 1 or a 0 thanks to centered orientation. you can shuffle in some ways a suduku grid and position more density of known data towrads the center then go from the center outward.
It took me 33 minutes to realize that he was wearing a Mario t-shirt...
There is a typo at 20:40-20:50, should be [ (A in NP ) --> (B in NP)] as reduction is saying B is at least as 'hard' as A is, this is the contrapositive of (B in P) --> (A in P).
exactly what I was thinking
Note that P is a subset of NP, not the complement of NP. Thus the contrapositive would be (A not in P) -> (B not in P), not what was claimed above.
If we think of the difficulty graph illustrated by the presenter, then problem A reduces to problem B amounts to A is at or to the left of B. So (B in NP) -> (A in NP) is accurate.
That is not a typo, it is a writo. I don't see him using any typewriter during this lecture.
First of all, if we can reduce problem A to B, it means B is not easier than A. If as you said "If A is in NP", then we cannot say anything about B since B could be NP or NP-hard.
Further, P is a subset of NP. if B is NP, then A could be P or NP. Therefore, it is still correct to say A is in NP. If B is P, then we know A must be P too.
The whole point is that B is the upper bound of A. It is meaningless to say "if A is xxx, then B is xxx
, since B can be anything harder than A. If we say "if B is xxx, then A is xxx", this is meaningful as we know the worst case complexity for A. This is what the professor wrote.
@@TheOYENDRILA First of all, if we can reduce problem A to B, it means B is not easier than A. If as you said "If A is in NP", then we cannot say anything about B since B could be NP or NP-hard.
Further, P is a subset of NP. if B is NP, then A could be P or NP. Therefore, it is still correct to say A is in NP. If B is P, then we know A must be P too.
The whole point is that B is the upper bound of A. It is meaningless to say "if A is xxx, then B is xxx
, since B can be anything harder than A. If we say "if B is xxx, then A is xxx", this is meaningful as we know the worst case complexity for A. This is what the professor wrote.
Why create the last crossover gadget instead of using pipes to move you where you need to be? Or was the spirit of the exercise to use the most basic implementation of Mario possible? Is the whole goomba/mushroom thing better? (Also, the final mushroom check can be a small tunnel of fire vines short enough for the hit invincibility to last, but full enough that small Mario can't pass.)
Expect Nintendo try taking down this video because he is wearing a Mario shirt and mentioned it in the video.
**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.
Thanks, ChatGPT
He explains it so good.
outstanding lecture! Finally got to comprehend np np complete and np hard!! Thanks!
Really really really helpful~ Thank you so much
Q on proving NP-completeness: if X is NP-Complete it belongs to both NP and NP-hard I understand that you have to show that X belongs to both sets. But if you have a reference NP-complete problem like 3SAT wouldn't it suffice to show that 3SAT is reducible to X? Why do you need step 1?
because any problem can be reduced to a no-less-hard problem. So if we show 3SAT is reducible to X, we only should X is no-less-hard than 3SAT. This only means X is in NP-Hard.
Step 1 is to show X is in NP.
3DM description is too NP-hard to understand! Still love this prof tho
This is where I had to hit pause, take a break and come back to it later. I need time to figure out just what exactly the problem is and by the time I have figured it out, the lecture will have gone on to many other things that I missed. I don't do too well with many abstract symbols.
Brilliant lesson
I think last two statements @ 23:44 are wrong, namely " B elem (N)P -> A elem (N)P"
because we can turn 2SAT into 3SAT and solve it
The point is that P is a subset of NP. So if B is NP, A could be P or NP, and it is not sure. But it is always safe to say A is in NP, because if A is in P, it is also in NP.
As far as I understood.
1) If B is in P, then A is also in P :
This is saying that if problem A can be converted to problem B in poly-time and if problem B can be solved in poly-time then it follows that you can also solve A in poly-time.
2) If B is in NP, then A is also in NP:
This is saying that if problem A can be converted to problem B in poly-time and if problem B belongs to NP i.e. its solution can be verified in poly-time, then A must also belong to NP. This doesn't mean that A cannot be faster than NP. Problem A could belong to P while also belonging to NP, as P is in NP.
14:17 NP Completeness Definition
guys, this is not an easy course, so if you don't understand or get lost, it's totally FINE! You are a NORMAL person!
I don't want to fail :(
@@dailyfightvideos4269 If you have the time, go back and watch it again. The pause button is your friend. With material like this, you have to walk before you can run. But once you've figured out how to walk, you might surprise yourself with how fast you can run.
i got lost once he started drawing the wheel. can anyone explain?
Wikipedia:
For each variable xi, there is a "variable gadget" shaped like a wheel. It is made of overlapping triplets. The number of triplets is twice the number of occurrences of xi in the formula. There are exactly two ways to cover all the vertices in the gadget: one is to choose all even-indexed triplets, and one is to choose all odd-indexed triplets. These two ways correspond to setting xi to "true" or "false". The "true" selection leaves uncovered exactly one vertex in every odd-indexed triplet, and the "false" selection leaves uncovered exactly one vertex in every even-indexed triplet.
For each clause xi u xj u xk, there is a "clause gadget" shaped like a rose. It is made of three overlapping triplets, one for each variable in the clause. It can be covered iff at least one of the nodes is left uncovered by the selection of the variable gadgets.
Since it is possible that two or more nodes are left uncovered, we also need a "garbage collection gadget". It is shaped like a larger rose. It is made of several overlapping triplets, one for each vertex that can be left uncovered in the variable gadget. The number of such gadgets is determined so that they can be covered exactly if and only if there is a satisfying assignment.
Self Note.. 17:15 NP Complete
He went Walter Lewin at 2:57
How so?
@@SwopCovers dat accidental dotted line he made when spelling the letter l in 'solvable'.
I would have liked to see Tetris since the game is easy to understand but playing it to win is NP Complete. Would have liked to see that proof. Seems you can reduce the jigsaw problem to Tetris to prove it is NP Complete.
Great lecture!
Bravo. This is good video, and very well presented.
Just call a group of possibilities out of the possibilities in a sudoku cell, then there should be so many 1's per adjacent row column and subgrid. This way of encoding the problem should be enough to smash np complete problems in p time
If we can't prove P = NP, can we prove P < NP?
"In my proposed solution, I introduce a novel computational paradigm that enables us to efficiently solve NP-complete problems in polynomial time. This paradigm revolutionizes the way we approach complex computations and leverages previously untapped connections between P and NP.
Through extensive testing and analysis, I demonstrate that this new paradigm effectively solves a wide range of previously intractable problems. The proof involves constructing a transformation algorithm that efficiently converts any given NP problem into an equivalent P problem, providing compelling evidence for the equality between the two classes.
The implications of this proposed breakthrough would be tremendous. Industries such as optimization, cryptography, and artificial intelligence would experience a significant leap forward. The ability to efficiently solve NP problems would enhance decision-making, accelerate scientific discoveries, and revolutionize various fields reliant on computation.
Where is that from?
i request ocw to record mit 6.045 pls
The game creation software is Unity from Autodesk.
Most "reasonable people" believe in the Axiom of Choice, yet we know that's hardly "reasonable."
The legal standard of "reasonable actor" applied to computational complexity theory wipes out constructivism in one burp. Thus 6.046J alienates arguably its greatest ally.
Why do we need poly size certificates here ?
How does he conclude that rectangle packing is weakly NP-Hard? In general, I’m a little confused about how he’s concluding NP strength/if/how it’s transferred with reductions. It makes sense to me how he showed subset sum to be weakly NP-hard, and maybe why partition was also therefore weak (because it is reducible to finding a subset sum of t?). It would make sense to me that any time you can reduce a problem A to a weakly NP-Hard problem B, that you could conclude that A must not be strongly NP-Hard (and that if A is NP-hard it must be weakly so). However, with rectangle packing we only did the one way reduction from partition to it. This doesn’t by itself guarantee that rectangle packing is weakly NP-Hard, does it? That is reducing a weakly NP-Hard problem A to some other problem B doesn’t guarantee that B is also weakly NP hard, does it? Otherwise every NP-Complete problem would be weakly NP hard, because some weakly NP Hard problem reduces to it, and clearly some NP-Complete problems are strong NP-Hard.
Now that I think back on it, an NP-Hard A -> weakly NP-Hard B reduction also doesn’t seem to imply that A is weakly NP-Hard, because any weakly NP-Hard problem being NP-Complete would imply all NP-Complete problems were weak, another contradiction. So how is he determining strength or weakness of these problems? Is it something I’m missing or just a detail he’s glossing over?
Thanks
I have a question about the proof strategy for a problem being in NP. It's said you let a non deterministic turing machine guess the good answer and then verify it in polynomial time, completing the proof. But how do you know that there wasn't an actual polynomial deterministic algorithm to get those guesses? By that reasoning, everything in P is actually NP if we just let a machine guess the right answers. What am I missing?
everything in P is actually in NP
Love it
Thank you so much.
23:25 Prove A Problem is NP Complete
I do not like the assumption that P = NP or P != NP that is made here; I do think this statement is independent of the basic assumptions.
why is there no x_5 or x_6 in the 3SAT example?
48:50 oh boy
last semester?
wow thanks
3d matching 46:27
If problem A can be converted to problem B(which is NP complete) in polynomial time then, what can we say about problem A?
Is problem A, NP then?
I think that nothing can be said about A. Can someone please confirm?
I believe you are correct that nothing can be said about A based off of 22:15 to 22:55
I believe the lecturer made a mistake here.
If problem A can be converted to problem B, then A is no harder than B. So if B is NP, then A must be at most NP (could be P but we don't know)
if B is P, then A must be at most P which is P.
@@zichaohu9301 no mistake.
If problem A can be converted to problem B, then A is no harder than B. So if B is NP, then A must be at most NP (could be P but we don't know)
if B is P, then A must be at most P which is P.
It depends. If B is P, then most certainly A is P. If B is NP, then we can relax and say A is at most NP, even when A in truth is P, given P is a subset of NP (we can reduce P to NP). It gets tricky though when B is NP-complete. If B is NP-complete and A could be reduced to B, shouldn't that mean A is both NP and NP-hard and therefore, NP-complete? And isn't that why, in order to prove the completeness of A, we first ensure A is NP and then try to reduce a problem Z which is NP-complete to A (essentially declaring that A is either equal to or harder than Z, i.e. NP-hard)? Now, if B is NP-hard and one can reduce A to B, only here we cannot say what exactly A is, i.e., A could either be NP or NP-hard or both (NP-complete).
Please correct me (with explanation) if I am wrong.
Thanks for lecture Sir ... :)
GOOD MORNING SIR
I didn't quite get how you said that the 3DM was NP? I get the reasoning but I am interested in the formal steps.
A nondeterministic machine would guess a true cover and check it in polynomial time. it checks that the problem is indeed an instance INST of 3D matching and it checks that the cover (the 3DM) covers XUYUZ both are done in polynomial time of the size of the input INST instance of the problem
Hi, whats the going text book for this class?
Can anyone explain the 3SAT -> 3DM reduction? Little confused
Not everything is a physical object so no P does not equal NP can be proven
is this statement about the overall nature of truth
Can someone please tell me when he says there is no polynomial time algorithm to solve 3 set problem, does he also mean polynomial time space or nothing about space?
He doesn't mean anything about space in his statement. It is related but this particular lecture has nothing to do with it.
got it, thanks!
see also 42:10 where he mentions checking size
why finding shortest distance between two points in 3d plain is np hard problem ?
Check out the A* "a star" algorithm. (www.redblobgames.com/pathfinding/a-star/introduction.html is good)
can someone explain the mario and clause reduction to me, or provide a link for theory.
Not being rude, but can someone explain the applications of such mathematics? What does this course teach and why is it useful? Thanks!
Courses like this are vital for understanding the deeper ideas of algorithms. Knowing such things might rarely bring you an direct advantage but it's good to know for understanding 'everything'
I can't speak for the whole course, but the concepts of computational complexity (this lecture) are useful for determining how efficient an algorithm is, or even how difficult a problem is. Practical instances of these mathematics can be found in cryptography and cryptanalysis. The RSA crypto-system is based on integer factorization, a problem which is in NP and Co-NP. This gives people an idea of how difficult RSA is to "break". Cryptanalysis has a number of different methods of attack, which can be categorized by efficiency (how much time or space an algorithm uses) using P, NP, and so on. This gives us an idea of how useful a theoretical attack is.
It's really important to know how hard is to solve a problem. Knowing that a problem belongs to the class of NP-Hard for instance might mean that it takes "forever" to be solved for large inputs, so we need to prune the solution space some heuristics first for example.
The guy doing the class is one of the smartest persons on earth but I usually don't like his teaching. See book "Introduction to the Theory of Computation" for a good coverage on these topics.
Impure Drunkard's Walk,
It's extremely odd of you to pick an interesting and sophisticated pseudonym like PureChaos if you don't already know the answers to your question here.
You very clearly don't live up to the good name your are discrediting.
No, Z*, that's wrong. You flunk. The specific material in this course will give anyone a bit of a handle on how long it will take to solve their problem.
It will also save some people tens of millions of dollars by telling them in advance not to bother wasting their money.
You really should not post to the Internet when you don't have a clue what you're talking about.
* Not Z1rk31. What Z1rk31 posts is correct and intelligent.
I see that Z has now removed their stupid post. Good.
Wait, so you are proving not that the game super mario is NP-hard but that you can construct NP-hard levels in mario? The fact that people have said Super Mario is NP-hard has always confused me.
It means you can't build a computer program guaranteed to find a way to the end of the Super Mario maze and win that level. At least that's what seems to be going on here. Can't build a robot to ace Super Mario Brothers, LOL
When we say Super mario is NP-hard, we are saying that it is harder or equally hard to every problem in NP (basically that every problem in NP reduces to Super mario). We already know that 3-SAT is NP-hard, so if we show that you can reduce 3-SAT to super mario bros, then Super mario bros is at least as hard as 3-SAT, meaning that Super mario is also NP-hard.
So in the proof we constructed some gadgets so that we can map any instance of 3-SAT to some instance of Super mario bros. Since this is possible, we have that 3-SAT reduces to Super mario bros and thus Super mario bros is NP-hard.
Tl;dr because we were able to reduce 3-SAT to Super mario bros. We know that Super mario bros is at least as hard as 3-SAT, if not harder, and so it too is NP-hard.
You said that I can put my calculations into a computer and it will tell me if I am right or wrong? No kidding
Why is this on my reccomendation? I don't even study whatever this subject is lol
The definition of NP at 3.45 min. is wrong! You do not guess one out of polynomially many options, but out of an exponential number of options (say a SAT problem on k variables has 2^k possible assignments, not k^{O(1)}). The adjective polynomial describes the time complexity of the checking function, not the number of options. If one could choose out of polynomially many options, one could simply enumerate the options and check each of them in polynomial time... which implies P=NP.
The definition is not wrong. You have to take into regard, that it follows the idea of non-deterministic computing. Thus the computational steps may be at least growing exponentially in any amount of time O(1). Polynomially many options are then given and it's possible to guess an option which resolves to YES. The time needed would be 0(1), of course.
If you were to enumerate those options and check all of them (in polynomial time, as you stated correctly), you would already have used non-deterministic computing and the overall effort would still be at least be k^{O(1)} for any given SAT(k).
See what you mean. But this is not what the guy says. He is talking about a "good guess which leads to a yes answer", which implies that a guess is a satisfying assignment for a set of variables. There are an exponential number of such guesses. In your interpretation he should have talked about about a set of guesses, one for each variable. I stick to my point ;-) But thanks for pointing this out to me. It explains why the confusion emerged....
This may clear things up: a non-deterministic Turing machine can solve a problem with an exponential number of options in polynomial time, and it can solve a problem with polynomial options in constant time. In his definition, of NP he's referring to the later case, where a deterministic machine would have to check through each of N^k possibilities, but an non-deterministic machine could guess which of the N^k possibilities is the right one. You can think of this process as occurring at each branching of an exponential problem, where there could be up to N^k branches to check. The non-deterministic machine knows which branch to take (and makes this choice N^k times moving down the tree), whereas the deterministic one has to check every branch.
I suggest to read Computational Complexity, Sanjeev Arora.
The options in the SAT problem which we guess are whether each variable is true of false. Those are constant and so are polynomial. You first guess the first variable, then the second and so on.
the alien example was funny
Can I communicate you in important thing that will change computer science 180 degree ?
I can solved np problem .
P, NP can complete is-is N is numbers of OOP both P Processes of CPU. both NP muitprocesser of systems😇🤗🎖️🌎
should NP be the set of decision problem that can be solved in polynomial time with Non-deterministic machine, or, the set of decision problems whose "TRUE" instances can be solved in polynomial time with ND machine. if the former, how is it different from co-NP
it is the later
How does this work or not work with the human brain? The most advanced computer ever designed.....
Gets too confusing from 40th minute.
If we have a problem A that is in NP and we reduce it to B then we know that B is NP. if we dont know if A is NP and we know that B is in NP are we sure that A is in NP?Could'nt be an algorithm that do not use this reduction but solves the A problem? is the second statement in ruclips.net/video/eHZifpgyH_4/видео.html correct?
A is at most in NP and no more harder. Of course A could be in P. But P is a subset of NP so his statement still holds. The whole point is that A cannot be harder than B, i.e. B is always on the r.h.s of A on the difficulty line he draw
@@junzhai1715 Seconded.
whz is watter not use to clear balckoabrd in mit?
27:59
I can't fully understand that @18:52, the professor stated that "X is NP-hard if every problem y ∈ NP reduces to X". Doesn't it mean that a problem(NP) would then reduce to a harder problem(NP-hard)? How should I interpret it? Thanks!
Yes, reductions are from easier to harder (or equal) problems. The word reduction is confusing in this aspect.
yes, we can reduce a problem to a no-less-hard problem
Reduction ... Time point ruclips.net/video/eHZifpgyH_4/видео.htmlm28s . Chalkboard writing .. then A element of P ... seems to disagree with the notes from the MIT site ... which is written A element of NP ... . Are the notes incorrect?
I have the same question.
but why everybody didn't ask questions, i think all students got it except meeee
Is there anything between polynomial and exponential? Is there anything that grows faster than n^C for every C, but slower than e^(n^ɛ) for every ɛ>0?
f(n) = e^sqrt(n) or n^log(n)
@@mardymsyz e^sqrt(n)=e^(n^0.5), so no.
n^log(n) could work, thanks
Could someone please help me understand what did he mean by, "Computer would guess an option from polynomially many options"? I am not able to think(and relate) of an example when an algorithm guesses while solving a decision-based problem. e.g. while determining a chess move. His next statement only adds to my confusion, "The guess is guaranteed to be a good one" :(
I don't know if this answer is too late, but: no computer can do this in real life! It's just a theoretical model, like if there were a computer that could always make the right choice in a decision based problem, it could do this in p time..
This makes a lot of things clearer to me, now I will re-watch it once. Thank you so much for your answer!
(tries to take notes)
- here's my mario level
why my mothertongue is not English..why... it makes hard thing harder
same problem, bro(((
just keep on learning! :)
Just waiting for him to solve time travel. Shouldn't be long. Lol...
Great example with the original mario bros game.
Why white chalk is used in MIT Courseware classes, despite the availability of new whiteboard black markers??
Super Mario Bros example was fun, but the 3DM explanation is really bad and doesn't make any sense, and he seems to be basing the rest of the reductions on that one. So 50 minutes pretty much wasted for me (plus the hour+ I used for rewatching the 3DM part again and again, and googling other explanations for it). Very much not recommended.
Maybe u are just dumb
What a cchad!
23 NP researchers disliked the video...:)
a question : you play lottory. chances 1: 14 Mil. for 6 out of 49 Numbers. What is the chances according to P vs. NP
I hope, i hear from u guys & girls🍻
You heard from no one after two years ☺️☺️☺️😁😁😁
I thought this was about Jungian Analytical Psychology lol. Wrong video
I have no idea what he’s talking about or what the subject even is. Sometimes I wish to know in a nutshell what this subject means and its purpose, while being in plain average IQ english and in one sentence. My brain is too ignorant and smol for this lol
To my understanding,
1. Most problem are very hard (NP-hard);
2. If you found that the solution to your problem can be used to solve some known NP-Complete problems, then you know your problem is NP-hard;
3. If you do solve your NP-hard problem efficiently (polynomial time), then you should examine it very carefully that it may bring you some awards.