16. Complexity: P, NP, NP-completeness, Reductions

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Erik Demaine

In this lecture, Professor Demaine introduces NP-completeness.

License: Creative Commons BY-NC-SA

[Francospain]

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

[valeriyv]

The first ever video on NP-completeness where I started to understand at least something. MIT is the best. The lecturer is brilliant.

[semajxocliw]

If you're looking for reductions specifically he starts defining it at 15:25

[kushraj]

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

[davidloter]

Just a regular joe here...I'm glad we have professors like this man, teaching those who understand the course(s).

[marinasalonso]

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

[enirmo]

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!

[shaunmiller]

His lectures are as brilliant as his shirts. Thank you for sharing!

[davidloter]

This Man Is A Genius. His Eyes tell me so. Looks like he has more to say than can be compiled.

[abhishekghosh]

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<=k<n ; n<=j<2n; 2n<=i<3n. Now corresponding to the element in a 3-tuple we place a 1 in the corresponding position in our array such that it forms a forms a number in base b as shown.

[JL-ixyz]

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

[yamanmalkoc]

So this is what freedom of information feels like

[wtw]

Dude's t-shirt collection is legendary.

[BELLAROSE]

**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.

[andrewwong]

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.)

[quosswimblik]

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.

[Giacccomo]

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!

[Zatocrew]

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?

[NewtonCazzaro]

Expect Nintendo try taking down this video because he is wearing a Mario shirt and mentioned it in the video.

[whatamitalkingabout]

i got lost once he started drawing the wheel. can anyone explain?