How do you 'solve' an NP Complete Problem?

In this episode, Dr. Know-it-all follows up on his previous P vs. NP video. This time he delves into how to do a "good enough" job solving these very difficult problems that the solution can be used in real-world scenarios like warehouse logistics or forest logging scheduling.

Here are some good links to learn more about the P vs NP problem.
NP problems and Polynomial time: Fortnow, Lance (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ: Princeton University Press. ISBN 9780691156491

Be sure to subscribe, and be sure to ask questions for Dr. Know-it-all in the comments (or at drknowitallknows at gmail)--anything from the mundane to the esoteric is fair game. See what his off-the-cuff answer is, and if it's right or wrong!

[iisuuguha_]

It was a very interesting video, your channel is quite underrated 😀👍🏻

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

[Bandit-]

Do quantum computers perform the same steps of "jumping around" during the temperature cooling process, or rather, are they searching all mins/maxes "concurrently" in the search space? Apologies--quantum computing is not my area.