Algorithms, heuristics and typical case complexity of hard problems

在过去的十年中，人们对组合搜索问题中的相变现象进行了广泛的研究，如命题可满足性（SAT）、约束满足问题（CSP）和图着色问题。这些问题在最坏情况下很难计算，但在人工智能和其他应用领域（如规划、调度和通信网络）中非常重要。人们对组合搜索中相变的研究越来越感兴趣，这是由于观察到随机实例的典型情况硬度与某些实例分布下解概率的相变密切相关。远离阈值，随机实例通常是约束不足（或约束过度）的，并且非常容易解决。然而，在阈值附近，极端困难的实例往往以高概率出现。在本研究计划中，我们从理论上和经验上研究了启发式算法在搜索算法中的效率、由特定概率分布随机生成的问题实例的典型情况复杂性以及各种问题结构（如问题表示（编码）、约束一致性、骨干、后门和结构对称性）之间的相互作用。目标是：(1)深入了解问题结构对不同启发式算法性能的影响，并为高效启发式算法的设计提供指导；(2)了解不同类别搜索算法的基本局限性；(3)针对现实问题开发算法解决方案。要研究的算法问题分为三类：(A)人工智能中感兴趣的传统np完全问题；(B)图论中具有特殊性质的特殊问题，如支配团问题和树宽度问题；(C)来自应用领域的问题，如通信网络中的系统发育重建问题和多约束路径问题。

During the past decade there has been an extensive study of the phase transition phenomena in various combinatorial search problems such as Propositional Satisfiability (SAT), Constraint Satisfaction Problem (CSP), and graph coloring. These problems are computationally hard in the worst-case, but are of great importance in artificial intelligence and other application domains such as planning, scheduling, and communication networks. The growing interest in the study of the phase transitions in combinatorial search is due to the observation that the typical-case hardness of a random instance is closely related to the phase transition of the solution probability under some instance distribution. Far from the threshold, random instances are typically under-constrained (or over-constrained) and are very easy to solve. Around the threshold, however, extremely hard instances tend to appear with high probability. In the proposed research program, we study theoretically and empirically the interplays among the efficiency of heuristics in search algorithms, the typical-case complexity of problem instances randomly-generated from certain probability distributions, and the various problem structures such as problem representation (encoding), constraint consistency, backbones, backdoors, and structural symmetry. The objectives are (1) to gain insight on the impact of problem structures on the performance of different heuristics and to draw guidance regarding the design of efficient heuristics; (2) to understand the fundamental limitations of different classes of search algorithms; and (3) to develop algorithmic solutions to real-world problems. The algorithmic problems to be investigated fall into three categories: (A) Traditional NP-complete problems that are of interests in artificial intelligence; (B) Specific problems in graph theory with special properties such as the dominating clique problem and the tree-width problem; and (C) Problems from application domains such as the phylogeny reconstruction problem  and the multi-constrained path problem in communication networks.