Kolmogorov复杂性及其应用

Kolmogorov复杂性，又称描述复杂性。它不同于经典的时间和空间复杂性。Kolmogorov复杂性是由Kolmogorov, Martin-Lof, Chaitin，Solovay等人创立并奠定基础的。它来源于对于概率论，统计学、信息论，可计算性理论、人工智能理论以及公理集合论的研究。Kolmogorov复杂性已经广泛地运用在许多科学技术领域，如信息科学、计算机科学中的人工智能理论、算法复杂性分析、组合理论、数学中的定理证明、物理学中的混沌学和力学、生物学中的DNA序列的复杂性、哲学以及机器学习理论等等。本课题拟对Kolmogorov复杂性的各种度的结构和性质进行深入的研究，并力求有所应用。