We already have a pretty good tool set for NP completeness. We have SAT. We have vertex cover.
We have independent set. We have clique.
And we have shortest tour, and I guess also traveling salesman.
In some way, it's amazing, isn't it? that all of those problems here are NP complete,
which means in a way they are equally hard to solve, although they are all quite different.
Now, I promise you a library of NP completeness.
What I'm going to give you now is four additional NP complete problems
that are often very very useful for showing NP completeness
or also for recognizing NP completeness, because even before you do a formal proof,
it's usually a good idea to say, "Oh, this problem just looks very close to SAT.
We better be careful. This could NP complete."
You don't always have to do the formal proof.
It can also be a good indication of how hard a problem could be.
Before additional problems, I would like to show you a problem called 3-SAT,
a problem called k-coloring, a problem called packing, and a problem called common substring.
So 3-SAT is basically SAT, but there's one restriction and that is that
each clause has exactly three variables and that of course is a nice assumption to make in
many proofs of NP completeness, because if you have exactly three variables in each clause,
these proofs often become easier to read and much cleaner.
As a side info, 2-SAT so where each clause has just two variables, a solvable in polynomial time.
So one number here can make a difference, and the resulting 3-SAT formulas look like this.
So you have three variables here in this clause then three variables here
and of course with another index and so on.
K-coloring asks if you can color a graph with k-colors so k is given as part of the input.
And what is meant by coloring is that you give each vertex a color such as here.
So we color this one red, this one red, this one green, and this one also green.
The constraint is you cannot color two vertices with the same color if they are connected by an edge.
So this here would not be allowed, and actually, the graph I've drawn here
cannot be colored with just two colors so you need three colors to color this graph.
This here for example would be one solution. It cannot be number two.
And of course that's stated as a question. So is it possible to color the graph using k colors?
For packing, you have given a number of containers and objects.
And the containers have a capacity, and the objects have a value and a capacity requirement.
So you have containers like these that come in different size and then you have objects.
You have little objects. You big objects. You have very big objects. And they all have different values.
So this might be not so valuable. This might be a little bit valuable, and this might be very valuable.
So usually you cannot put all of these objects here into the containers.
So the question is what is the maximum value that you can put into the containers?
And of course, you could have the case that, for example, the bigger object
is actually worth less than the smaller object so there are lots of different combinations here
and will actually investigate this problem a little bit more in one of the next units.
Now, common substring is actually a misleading name because some people use this in a wrong way
I've seen this happened before. It actually should be called common subsequence.
If somebody says common substring, better ask them if they don't mean common subsequence
because common substring is actually not an NP complete problem,
and common subsequence is the following problem.
You're given two strings so string one and string two. Let's say lemonade and blender.
And what's the difference between a substring and a subsequence?
A substring is always lots of characters that are one after the other.
For a subsequence, you can basically skip certain characters.
So e, n, a, e is a subsequence of lemonade but not a substring.
And actually, we will do this as a little brief quiz.
What is the longest common subsequence of lemonade and blender?