随机复杂系统特别是以NP完全问题为代表的大规模随机约束满足问题复杂性的研究，与新千年的世界七大数学难题之一密切关联，是理论计算机科学和数学领域所关注的核心基础问题。对这一问题的科学研究不仅可以从基础理论上探索计算复杂性形成的根本原因，而且可以从数学和物理的学科交叉观点解释相变现象的本质内涵。本文主要研究约束满足问题自身求解的高度计算复杂性与其解空间的复杂几何结构之间的对应关联关系。　　 基于统计物理学中阻挫的基本思想，本文针对一般的组合优化问题提出了具备代数学形式的交互阻挫这一概念，并基于Spin Glass理论中的系综对称理论对2—SAT、3—SAT中的交互阻挫结构进行了分析计算，结合交互阻挫的自身特点，得到了其对于一般局部搜索算法和启发式算法的有效性分析，使得本文可以从一个新的角度来看待系统解空间的分簇、骨架变量等特殊几何结构；计算了顶点覆盖问题中的交互阻挫现象，论证了长程交互阻挫的存在性(在平均度c=e出现)，从而证明了顶点覆盖的分簇现象以及其分簇特点。同时，基于交互阻挫这一等价关系，本文从解空间的角度反过来分析研究随机网络拓扑结构，对随机网络上连通分支数、圈数等特征结构进行了分析估计；对于铁磁Ising model统计分析了其拓扑结构特征与基态空间结构特征的关联性，利用Cavity方法得到了两者复杂性之间的定量分析。　　 从一般的约束满足问题以及有限域Z2上的代数多项式方程组出发，作者提出了一类新的NP完全问题：海量代数系统，一类形式简洁的多项式系统。这种系统可以将NP完全问题转换为两类P问题的联立，XORSAT问题和MAS—nonlinear问题，而这两个子问题的解空间分别具备群和半群性质。利用问题因子图上的阻挫信息传播机制，本文对于这两个子问题解空间生成元的构成方式以及数量规模进行了研究分析，建立了一系列解空间的非满足性相变点的代数学对应和诠释，实现了(长程)交互阻挫现象的严格计算及拓扑对应，给出了一阶、高阶系综对称破缺现象的代数学刻画。同时基于所得到的研究结果给出了求解一般约束满足问题的一类完全算法设计思路。　　 本文主要从大规模随机约束满足问题因子图上的信息传播机制入手，从信息传播模式和范围的变化出发，精细探索了解空间结构特征，从代数学角度对其解空间实现了严格描述和研究。结合Belief Propagation和Survey Propagation算法，对于NP完全问题的计算复杂性进行了从解空间几何和代数结构特征的崭新刻画。