Congratulations! You have now learned a lot about solving NP complete problems in practice.
You have learned about search tree optimizations, you have learned about pre-processing,
and you have learned about other techniques such as fixed parameter tractability, and this is huge.
Now, of course, in this unit, I could only teach you the very basic techniques that I use.
So you might be wondering, what is the state of the art for solving NP-complete problems in practice?
I would like to give you a few examples and numbers.
For vertex cover on practically relevant inputs, you can sometimes find the vertex cover
progress with over 10,000 vertices for independent set and clique.
Independent sets and cliques have been calculated for many graphs with over 1000 vertices
and traveling salesman which is very close to shortest tour
and actually sometimes people also solve shortest tour, so a traveling salesman,
you really have to be specific what kind of problem your are talking about.
But there's one example where somebody solved an instance with ≥85,000 vertices.
Think about what this means for the four computer scientists
that we met throughout this course so far as started out with not being able to solve vertex cover for
a graph with 10 or 20 vertices and then she learned about NP completeness.
Her situation was actually quite dire, but then we showed her that there's search tree optimization
and pre-processing and if those techniques are applied in the right way,
then, Alice can't certainly expect to be able to solve her problem
if she is working with 500 or 1000 vertices, because the thing is this,
the instances for vertex cover that come up in practice
are actually much easier to solve than worse case instances.
One example is this, you're practical instances went up to 10,000 vertices.
I think Alice can be pretty happy. What about Bob and Carol?
Bob and Carol, of course, they started out being as unhappy as Alice
because they also had impractical algorithms and then they found out about NP completeness.
Of course, they can also use search trees and pre-processing,
but their problems turn out to be harder to solve than vertex cover in general.
Even so, I think they should be a little bit happy because for the problems that they try to solve
in Genetics and in Finance, I think being able to work with about 1000 vertices should be okay.
And again, we have to assume that, of course, they are working with inputs
that are more easily solvable than worse case inputs but usually in practice, again, that's the case.
What about Dave, who we met very late in this course?
Well, when we met Dave, we showed a very complex proof that his problem was NP-complete,
so he started out very unhappy as well, I would assume.
And actually I think he stayed unhappy throughout this unit
because whenever we came across shortest tour or traveling salesman,
we always had to say, well, we're not really quite sure on how to do this.
This is an open research problem.
But then again, since this problem is so highly relevant in practice,
there have been lots of developments regarding sophisticated algorithms
that work very well in practice, so we can basically put it like this.
From a theoretical perspective, Dave has to be very very unhappy,
but if he uses sophisticated algorithms, then actually Dave can be the happiest of all
because the algorithms that have been developed for traveling salesman
work extremely well in practice.
And finally, of course, we should also say a little bit about SAT.
For the satisfiability problem, there are annual competitions and these competitions, of course,
are based on mostly on instances that occur in practice
than on instances that are deliberately hard.
And yet so, each year, usually instances are solved with over 1000 variables.
Now SAT is a problem that behaves very differently.
So there are some instances of SAT even with 10,000 or 100,000 variables
that are very very easy to solve because pre-processing is very effective for these instances.
And then there are other instances for SAT that just have a few 100 variables
that are super super hard to solve, so there, you usually need to try
a lot of different packages and techniques, but nevertheless,
when you come across an instance of SAT
and there are certain practical situations but this is the case, then you shouldn't despair.
SAT, again, if you're working with real world instances, for SAT, it's usually worth a try to solve it.