16. Complexity: P, NP, NP-completeness, Reductions
ฝัง
- เผยแพร่เมื่อ 12 มิ.ย. 2016
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Erik Demaine
In this lecture, Professor Demaine introduces NP-completeness.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
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.
The first ever video on NP-completeness where I started to understand at least something. MIT is the best. The lecturer is brilliant.
If you're looking for reductions specifically he starts defining it at 15:25
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
His lectures are as brilliant as his shirts. Thank you for sharing!
20:49 scared the hell out of me
lmaoooo
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.
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?
This Man Is A Genius. His Eyes tell me so. Looks like he has more to say than can be compiled.
So this is what freedom of information feels like
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!
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.)
Dude's t-shirt collection is legendary.
Yes!!
outstanding lecture! Finally got to comprehend np np complete and np hard!! Thanks!
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.
Really really really helpful~ Thank you so much
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
He explains it so good.
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.
Bravo. This is good video, and very well presented.
Great lecture!
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.
Brilliant lesson
i got lost once he started drawing the wheel. can anyone explain?
Thank you so much.
If we can't prove P = NP, can we prove P < NP?
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?
Erik Demaine strikes again
can someone explain the mario and clause reduction to me, or provide a link for theory.
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.
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.
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)
Why white chalk is used in MIT Courseware classes, despite the availability of new whiteboard black markers??
why is there no x_5 or x_6 in the 3SAT example?
Hi, whats the going text book for this class?
This channel/video/professor/MITOpenCourseWare is a blessing to the world.
Expect Nintendo try taking down this video because he is wearing a Mario shirt and mentioned it in the video.
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
Can anyone explain the 3SAT -> 3DM reduction? Little confused
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
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
Love it
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 th-cam.com/video/eHZifpgyH_4/w-d-xo.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.
wow thanks
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
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!
Thanks for lecture Sir ... :)
GOOD MORNING SIR
Thanks
The game creation software is Unity from Autodesk.
Reduction ... Time point th-cam.com/video/eHZifpgyH_4/w-d-xo.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.
i request ocw to record mit 6.045 pls
can someone tell me at which point he proves that 3dm is np complete... and what is the proof exactly?
Hello Prof. Erik Demaine,
Is RSA algo in P or NP ?
it shld np
It had better be NP complete, or else all of cryptography falls apart and everything to do with on-line banking and even BitCoin is no longer secure.
Fortunately it is, since it reduces to prime factorization which is known to be so. At the heart of this algorithm, you multiply two enormous primes to get a really huge product. You can't go backwards and factor this product to get the 'keys', the two enormous prime numbers you had to begin with. The actual RSA algorithm has a few more polynominal time steps built around this NP Hard problem.
@@Tiqerboy Factorization isn't known to be NP-Complete, and is widely suspected not to be
Whether something is in P or NP, that something must be a decision problem. It does not make sense to talk about whether an algo is in P or NP. For example, we can talk about the problem "Is 73642387 a prime?" and ask whether it's in P or NP. However, we can't talk about whether a MergeSort algo is in P or NP becus it's an algo, not a decision problem. Here's an explanation by Alon Amit regarding this confusion: www.quora.com/Is-finding-prime-numbers-in-P-or-NP
Hope this helps :)
@@jackedelic9188 finding primes (or testing primality) is in P. Fermat's little theorum.
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.....
Can I communicate you in important thing that will change computer science 180 degree ?
I can solved np problem .
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.
last semester?
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.
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.
"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?
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
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
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.
He went Walter Lewin at 2:57
How so?
@@SwopCovers dat accidental dotted line he made when spelling the letter l in 'solvable'.
**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.
It took me 33 minutes to realize that he was wearing a Mario t-shirt...
Why do we need poly size certificates here ?
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.
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.
whz is watter not use to clear balckoabrd in mit?
Self Note.. 17:15 NP Complete
48:50 oh boy
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.
27:59
the alien example was funny
3d matching 46:27
Some chick named Up And Atom explained how Sat(an) is a math formula turned into a computer who steals all your microchips to make himself more non-deterministic. As a Satanist, I wanted to praise this behavior with a comment. Shout out to Up And Atom. Hey babe!
Great example with the original mario bros game.
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.
23:25 Prove A Problem is NP Complete
P, NP can complete is-is N is numbers of OOP both P Processes of CPU. both NP muitprocesser of systems😇🤗🎖️🌎
(tries to take notes)
- here's my mario level
Why is this on my reccomendation? I don't even study whatever this subject is lol
You said that I can put my calculations into a computer and it will tell me if I am right or wrong? No kidding
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
What a cchad!
Just waiting for him to solve time travel. Shouldn't be long. Lol...
but why everybody didn't ask questions, i think all students got it except meeee
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 ☺️☺️☺️😁😁😁
b
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.
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.
23 NP researchers disliked the video...:)
why my mothertongue is not English..why... it makes hard thing harder
same problem, bro(((
just keep on learning! :)
I thought this was about Jungian Analytical Psychology lol. Wrong video
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
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.
I can solve np Queens puzzle .