数据流模型与判定树模型中的几个问题研究

项目名称： 数据流模型与判定树模型中的几个问题研究

项目编号： No.61170062

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 计算机科学学科

项目作者： 孙晓明

作者单位： 中国科学院计算技术研究所

项目金额： 57万元

中文摘要： 关于问题难解性的研究是计算复杂性研究领域最核心的问题，证明强的复杂性下界长期以来一直是理论计算机科学领域、乃至数学领域具有挑战性的课题，亟待理论和方法的创新。本项目计划在数据流模型和判定树模型两方面探索证明强的复杂性下界的新方法。在数据流模型中，一个关键的科学问题是如何能够使用尽可能少的存储空间来完成海量数据的处理，我们计划研究最短路问题、最大子团问题等几个问题的最优空间复杂度下界，力争提出流模型下证明最优空间复杂度下界的新方法。在判定树模型中一个重要的科学问题是对sensitivity复杂度下界的刻画，我们计划研究关于图性质的Turan猜想等几个问题，发展证明sensitivity复杂度下界的新技术，揭示其与block sensitivity复杂度之间的内在联系。

中文关键词： 通信复杂性；判定树复杂性；流式算法；计算复杂性；

英文摘要：

英文关键词： communication complexity；decision tree complexity；streaming algorithms；computational complexity；