NP最优问题的概率近似算法设计和平均复杂性设计

本项目主要对于NP最优问题的随机算法，近似算法及平均复杂性和用于计算机安全领域的数论算法的随机性分析和平均复杂性进行研究。对于NP优化问题给出了一种新的归约和逻辑定义，使得对数近似度的NP优化总是从常数近似度及多项式近似度的NP优化问题中分离出来。对集合论和图论中的某些经典问题给出了新的随机和褪随机算法。从计算复杂性的角度对零知识证明进行了较为深入的研究并给出了一个随机自归约的四步零知识证明协议并给出了新的可靠性定义。此外，对计算复杂性尤其平均复杂性在构造安全的系统的应用给予了探讨，并基于此给出了几种安全的系统构造方案。