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

计算问题

• 批准号: 249898-2011
• 负责人: Stege, Ulrike
• 金额: $ 1.75万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=547442
• 关键词: Computational; problems; tractable; algorithms; Bridging

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.

复杂性理论为我们提供了理解计算问题有多难的工具。经典复杂性区分了在多项式时间（P）内可解的问题和难以处理的（NP难）问题，并且可能不在P中。参数化复杂性对棘手的问题采取了精细的观点。它区分了对于所选参数来说是固定参数可处理（fpt）的问题和可能不具有此属性的问题。FPT算法的运行时间不以P为单位，但只要参数值不太大，就可以处理。我们调查了生物信息学，数据匿名化和认知科学领域的问题的易处理性。在生物信息学中，我们对序列分析问题感兴趣。在这方面，我们考虑两种类型的棘手性：NP-硬度和大输入尺寸。对于这两个我们开发易于处理的精确算法，前者使用的方法从参数化的复杂性，后者使用外部存储器的方法。精确算法帮助生物学家评估他们用于分析数据的模型。在数据匿名化中，我们调查要处理的数据集，以使来源无法识别，同时尽可能少地修改原始数据。数据匿名化问题在我们的技术和面向互联网的世界中非常重要;快速匿名化数据的能力非常重要。许多是NP难的，并且通常只有不精确的方法，如果有的话，在实践中存在。我们的目标是设计FPT算法来解决这些问题。在认知科学中，一个目标是了解人类在决策过程中处理什么问题（认知理论）以及他们应用什么方法来解决这些问题。据观察，人类往往擅长解决一些困难的计算问题。精确算法在工业中的应用将提高工业算法的质量。解决方案的最优性保证将提高学术界和工业界数据评估的质量。认知建模的研究成果将对认知心理学家识别新理论的能力产生重大影响。