2. 3-Partition I
HTML-код
- Опубликовано: 21 дек 2024
- MIT 6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs, Fall 2014
View the complete course: ocw.mit.edu/6-8...
Instructor: Erik Demaine
In this lecture, Professor Demaine introduces the concept of 3-partition and its many variations, a starting point for NP-hardness reductions. Weak and strong NP-hardness proofs are seen in the context of other examples.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
I'm amazed that these videos haven't had tens of thousands of views yet... what a fantastic opportunity given to everyone by MIT. Loving the content, really enjoying these.
I was reading your paper "Tetris is hard, even to approximate" and then I landed here, also by the legend E. Demaine😅❤
awesomely explained! I was totally lost with the Garey Johnson. Thanks a bunch!
At what point in the video does he prove that 3-Partition is strongly NP-hard?
Why can we assume that all a_i are in (t/4,t/2) ??
You Rock MIT!
cool
I'm so dumb I didn't laugh at 6:15
if you solve one problem proven to be NP- Complete, does that also solve PvsNP by default?
+Dan Diaz Since all NP-complete problems are NP-hard and each NP-hard problem is as hard as any other NP-hard problem, this implies that if we can show that a proven NP-complete problem can be solved in polynomial time then by reduction we can show that all NP-hard problems can be solved in polynomial time. Hence P = NP, but this is highly unlikely.
Yes, I think
If a problem is NP-complete, then every problem in NP can be reduced to it in polynomial time. Therefore, if you found a polynomial time algorithm for an NP-complete problem, then you would have a polynomial time algorithm for all NP problems because you could reduce them to the NP-complete problem in polynomial time, then solve in polynomial time. So P=NP. If P does not equal NP, then no NP-complete problem is solvable in polynomial time.