R8. NP-Complete Problems

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Amartya Shankha Biswas

In this recitation, problems related to NP-Completeness are discussed.

License: Creative Commons BY-NC-SA

[karansvnit]

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

[MNMLSTN]

My dude walked in straight from the afterparty. Respect!

[ahmedrek]

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

[hassanalamri]

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

[unknown]

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

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

[sumanmondal]

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

[luisribeiro]

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

[alexba]

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

[therealaverma]

Amazing video overall, really appreciate it.

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

[AndrewLvovsky]

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

[hj]

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

[JikeWimblik]

so you have you x by x latin square, lets say half the number in x are =1 and the other half of the numbers are =2, now we have a second latin grid with 1's and 2's, if we can solve that grid fast then we can rule out around half the possible numbers on the main latin square. Don't believe me try it for yourself. the real question is how long does it take to solve the 1's and 2's latin squares not whether the transformation works it works and should be easy to prove it works.

[xcx]

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

[badpoochi]

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

[atwith]

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

[badpoochi]

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

[FaNTaCoLa]

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

[droliaonfire]

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

[kutilkol]

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