A tourist guide through computational complexity
This talk is intended to give a brief overview on the concepts
involved in compu tational complexity. Along the way, we will provide
an introduction to the theor y of NP-completeness. We will also
introduce approximation algorithms and parame terized complexity.
In this talk I will focus mainly on two themes:
-
What is the significance of NP-complete results and approximation algorith
ms ?
-
What are the benefits of parameterized complexity ?
Most of the concepts introduced here will be given by referring to
problems oiginating from molecular biology.
Back to the schedule