基于相变现象的算法设计与难解实例构造研究

从平均复杂性的角度对NP完全问题的相变现象进行研究，分析解的结构与平均复杂性的关系；分析本课题组所提出的RB模型的难解性并研究如何利用这种难解性构造可满足的难解实例。力争对相变现象的本质有一个更清晰的刻划，加深对NP完全问题的认识。在理论研究的基础上，设计求解SAT和CSP的有效算法，并应用于海量信息系统中的若干实际问题。