Exact algorithms for NP-hard problems

我们建议研究精确算法的NP难问题。算法可以被看作是解决问题的一组构造。精确算法是一种能够最优地解决问题的算法。NP-难问题是一种特殊的优化问题，对于这种问题，很可能不存在多项式时间（即快速）算法。作为NP难问题的一个例子，我们可以考虑旅行商问题（TSP）。在这个问题中，一个旅行推销员必须通过许多城市进行旅行，从城市1出发并返回城市1，这样总的旅行距离是最小的。当然，通过计算每个行程的距离，然后选择具有最小距离的行程，可以将这个问题解决为最优。这个简单的算法花费了大量的计算时间。已经在一个相对较少的城市的情况下，这个问题不能解决（在合理的时间内）在任何现代计算机上使用这种算法。我们的研究将导致更快的算法，这类问题。即使是一个更快的精确算法，不运行在多项式时间已经意味着在实践中更大的实例（参见。在TSP中有许多城市）可以解决。其次，我们希望我们的研究将导致更好地理解NP难问题的（最坏情况下）解决它们所需的时间。由于它是非常不可能获得多项式时间算法这类问题，我们不能期望开发精确的算法，是快于一定的阈值。通过为一些NP难问题开发更快的算法，我们希望找出不同问题的阈值是否以某种方式彼此相关。

We propose to study exact algorithms for NP-hard problems. An algorithm can be seen as a set of constructions for solving a problem. An exact algorithm is an algorithm that solves a problem to optimality. NP-hard problems are a special kind of optimization problems for which most probably no polynomial time (i.e. fast ) algorithm exists. As an example of an NP-hard problem we can consider the travelling salesman problem (TSP). In this problem a travelling salesman has to make a tour through a number of cities starting and returning to city 1 in such a way that the total travel distance is minimal. Of course, it is possible to solve this problem to optimality by computing the distance of every tour and then choosing a tour with minimum distance. This simple algorithm costs a huge amount of computation time. Already in the case of a relatively small number of cities, the problem can not be solved (within reasonable time) on any modern computer that uses this algorithm.Our research will result in faster algorithms for this kind of problems. Even a faster exact algorithm that does not run in polynomial time can already mean that in practice much larger instances (cf. with many cities in TSP) can be solved. Secondly, we hope that our research will lead to a better understanding of NP-hard problems with respect to the (worst-case) time it takes to solve them. Since it is very unlikely to obtain polynomial time algorithms for this kind of problems, we can not expect to develop exact algorithms that are faster than a certain threshold. By developing faster algorithms for a number of NP-hard problems we hope to find out whether thresholds for different problems are somehow related to each other.