Computational problems & tractable algorithms: Bridging the gap between problem definitions and solutions

点击翻译按钮获取中文摘要

Complexity theory provides us with tools to understand how difficult a computational problem is. Classical complexity distinguishes between problems that are solvable in polynomial time (P), and problems that are intractable (NP-hard) and likely not in P. The list of NP-hard problems is long. Parameterized complexity takes a refined view on intractable problems. It distinguishes between problems that are fixed-parameter tractable (fpt) for a chosen parameter and problems that likely do not have this property. Running times of fpt algorithms are not in P but can be tractable as long as parameter values are not too large. We investigate the tractability of problems in the areas of bioinformatics, data anonymization and cognitive science. In bioinformatics we are interested in sequence analysis problems. In this area, we consider two types of intractability: NP-hardness and large input sizes. For both we develop tractable exact algorithms, the former using methods from parameterized complexity, the latter using external memory methods. Exact algorithms help biologists evaluate their models used to analyze data. In data anonymization, we investigate data sets that are to be processed to make the sources unidentifiable while modifying the original data as little as possible. Data anonymization problems are important in our technological and internet-oriented world; the ability to anonymize data quickly is highly relevant. Many are NP-hard and often only inexact methods, if any, exist in practice. Our objective is to devise fpt algorithms for solving these problems. In cognitive science one goal is to understand what problems (cognitive theories) humans tackle in decision making and what methods they apply to solve them. It has been observed that humans tend to be good in solving instances of some hard computational problems. The use of exact algorithms in industry will improve the quality of industrial algorithms. Optimality guarantees of the solutions will improve the quality of the evaluation of data in academia and industry. The research findings in cognitive modeling will significantly impact the ability of cognitive psychologists to identify new theories.