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.