數據結構的驗證複雜性下界研究

《數據結構的驗證複雜性下界研究》是依託南京大學，由尹一通擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：數據結構的驗證複雜性下界研究
• 項目類別：青年科學基金項目
• 項目負責人：尹一通
• 依託單位：南京大學

項目摘要

數據結構是計算機科學的基礎內容之一。數據機構複雜性理論探討的是對數據的有效表示可以最佳化何種類型的計算，這個深刻的理論話題對於人類對計算本質的理解有著重大的理論意義。另一方面，在現實套用中，人們期望解決的大量現實問題都是關於數據的某一類信息的查詢，可以被抽象成為不同形式的數據結構問題，因此，數據結構複雜性理論的研究也具有相當的現實指導意義。現有的數據結構複雜性理論面臨著理論工具單一、理論體系不完備、以及不能適應新體系結構發展需求的問題。本課題將通過對數據結構的驗證複雜性的研究，為數據結構複雜性分析提供新的理論工具，完善關於非確定數據結構複雜性的理論體系，並針對新的計算機體系結構建立與之相適應的數據結構複雜性理論。

結題摘要

本項目取得了如下研究成果：（一）對數據結構下界的兩大工具“豐富性引理”和“直和-豐富性引理”，證明了他們對於數據結構的驗證複雜性仍然成立。從而將所有使用這兩條引理證明的複雜性下界同時推廣到更強的非確定模型中。並且對於最重要的數據結構問題之一——高維最近鄰問題，得到了更高的複雜性下界。（二）對於並行體系結構，例如多核 CPU 或者MapReduce 模型中的數據結構，提出了並行數據結構的理論模型low-contention data structure，並系統的研究了負載均衡對並行數據結構的時間和空間複雜性的影響。（三）對於基於大數據上的計算所引發的新類型的算法問題——計數問題，發展了基於相關性衰減的理論工具，對於一系列根本的計數問題，包括：獨立集、圖著色、2元約束滿足問題等，得到了目前最好的算法。 該項目的多篇論文發表於理論計算機科學的頂級會議SODA'12, SODA'13（2篇）, FOCS'13等。