RB模型的结构参数研究

在约束满足问题中，给定一组变元和一组约束条件，求变元的一组赋值来满足所有的约束条件。很多实际中经常遇到的NP难问题(如布尔可满足性、图着色等问题)都是约束满足问题的特例。在随机约束满足问题中，通过一个随机过程来产生实例。随机约束满足问题可以出现可满足性相变现象，实验表明难解实例都集中在可满足性相变点附近。RB模型是近年提出的一种值域可变的随机约束满足问题，具有精确相变现象和很多难解实例。本文分析了RB模型的两种常见的结构参数：最小环割集和树宽度，证明了最小环割集和树宽度渐近等于变元个数。由于一些常见的求解算法的运行时间以这些结构参数作为幂指数，本文的结果说明这些算法的运行时间都是指数的，因此刻画和解释了RB模型的难解性。