Investigations into the nature of hard problems

许多优化问题需要在大量可能的解决方案中进行搜索，以获得最佳解决方案。例如，从船员的日程安排到计划，再到解决组合难题。这些问题往往很难解决，因为它们涉及到所谓的“组合爆炸”。基本上，这意味着稍微增加问题的规模，比如从100个单位增加到110个单位，可能会导致必须考虑的案件数量极不成比例地增加。我的研究试图理解为这类问题开发有效算法所固有的问题。即使在一个问题中存在指数爆破的可能性，该问题的许多大型实例在实践中也可能很容易解决。试图了解是什么区分了困难和简单的情况，这是开发更好算法的方法之一。

Many optimization problems require a search over vast sets of possible solutions for the best solution. Examples range from the scheduling of crews to planning to solving combinatorial puzzles. These problems are frequently very difficult to solve because they involve what is called ``the combinatorial explosion''. Basically, this means that increasing the size of the problem a little bit, say from 100 units to 110, may cause a hugely disproportionate increase in the number of cases that have to be considered. My research attempts to understand the issues inherent in developing effective algorithms for problems of this type.  Even when the possibility of exponential blow-up lies within a problem, many large instances of the problem may be easy to solve in practice. Trying to understand what distinguishes the hard from the easy instances is one of the approaches to developing better algorithms.