Communication Complexity, Proof Complexity, and Approximation

通信复杂性、证明复杂性和近似

• 批准号: 0514870
• 负责人: Paul Beame
• 金额: $ 20万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-06-01 至 2009-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514870&HistoricalAwards=false
• 关键词: Communication; Complexity; Proof; Approximation

This proposal encompasses three main subjects of research within the general field of computational complexity. They consider (1) communication complexity: the measure of the amount of information required by computationally unbounded entities in a distributed environment to compute shared functions of inputs that are not available to all entities, and (2) proof complexity: the complexity of expressing proofs of propositional logic tautologies (and unsatisfiable formulas) as a function of the size of these tautologies. Approximation plays a role in the research in both of these areas.Intellectual Merits Tradeoffs between the time and space used to solve computational problems are fundamental in computational complexity. In many instances one can save space by employing more time to recompute intermediate results rather than storing them. Moreover, the relationship between time and space is one of the major open questions in computational complexity. One of the most important is whether or not every efficiently-solvable problem can be solved using small space. Computational complexity is the key to the best methods of analysis for time-space tradeoffs but more powerful models of computational complexity are required to analyze comptutation at a finer-grained level. Massive data sets have become ubiquitous and are growing faster than random access memories. To handle these massive data sets efficiently, algorithms must use the fact that data can typically be transferred more quickly sequentially. Moreover, as in the internet context, the data can be evanescent. These features have led to the study of streaming algorithms which compute properties of datasets based on a single sweep through the unordered data. To keep the space requirements of these algorithms small and feasible, the answers produced are necessarily approximations. Analysis of communication complexity has been the major tool for studying streaming algorithms but existing results on approximation problems are very limited. By Cook's theorem, the existence of proof systems whose proofs are polynomially-bounded in the sizes of the input formulas is equivalent to NP = coNP. Although such an understanding is the ultimate goal of proof complexity, proof complexity also has many applications in the design of inference systems that are useful in practice and important for understanding the complexity of NP-hard problems.Research Topics The proposed research encompasses all three of these areas: (1) research on new models of communication complexity with the goal of obtaining stronger time-space tradeoff lower bounds. (2) research on a systematic study of approximation problems in communication complexity with the goal of obtaining bounds for a wider variety of problems using streaming (and related) algorithms. (3) research onproof complexity including the use of proof complexity in analyzing approximation algorithms, connections to communication complexity, search algorithms on satisfiable instances (including random instances), and more powerful inferencing algorithms.Broader Impact The proposed research on proof complexity has direct relevance to algorithms for satisfiability search and general automated inference, tasks which are major tools in AI and formal verification. Researchers in statistical physics and AI have suggested a strong connection between the properties of phase transitions in random problems and their associated computational complexity. Recent research on proof complexity by the PI and others has shed light on the connections between these areas. The PI has a record of interactions with researchers in statistical physics and AI. The proposed research will continue work on briding the gap between the methodologies of statistical physics, combinatorics and theoretical computer science and will encourage the cross-fertilization of ideas. Communication complexity is so fundamental that it necessarily impacts a broad range of topics within computer science. The list of impacts of the known techniques already encompasses applications ranging from properties of OBDDs used in formal verification to the efficiency of VLSI layout to streaming algorithms in database systems. The proposed research on the communication complexity of approximation problems will yield a body of results for application to streaming algorithms and will permit the extension of these notions to graphics pipelines as well.

这个建议包括在计算复杂性的一般领域内的三个主要研究课题。他们考虑（1）通信复杂度：计算无界实体在分布式环境中计算并非所有实体都可用的输入共享函数所需的信息量的度量，以及（2）证明复杂度：将命题逻辑重言式（和不可满足公式）的证明表达为这些重言式大小的函数的复杂度。 近似在这两个领域的研究中都扮演着重要的角色。智力优势用于解决计算问题的时间和空间之间的权衡是计算复杂性的基础。在许多情况下，可以通过使用更多的时间重新计算中间结果而不是存储它们来节省空间。此外，时间和空间之间的关系是计算复杂性的主要开放问题之一。其中最重要的一个是是否每个有效解决的问题都可以使用小空间来解决。计算复杂性是时空权衡的最佳分析方法的关键，但需要更强大的计算复杂性模型来分析更细粒度的计算。 海量数据集已经变得无处不在，并且比随机存取存储器增长得更快。为了有效地处理这些海量数据集，算法必须利用数据通常可以更快地按顺序传输的事实。此外，就像在互联网环境中一样，数据可能会消失。这些功能导致了流算法的研究，该算法基于对无序数据的单次扫描来计算数据集的属性。为了保持这些算法的空间需求小且可行，产生的答案必须是近似值。通信复杂性分析一直是研究流算法的主要工具，但现有的近似问题的结果非常有限。 根据库克定理，证明系统的存在性，其证明在输入公式的大小上是多项式有界的，等价于NP = coNP。虽然这样的理解是证明复杂性的最终目标，证明复杂性也有许多应用在推理系统的设计，在实践中是有用的，重要的理解NP-hard problems.Research Topics的复杂性，建议的研究包括所有三个领域：（1）研究新的通信复杂性模型的目标是获得更强的时间-空间权衡下界。(2)对通信复杂性中近似问题的系统研究进行研究，目标是使用流（和相关）算法获得更广泛问题的边界。(3)研究onproof复杂性，包括使用证明复杂性分析近似算法，连接到通信复杂性，搜索算法的可满足的实例（包括随机实例），和更强大的推理algorithm.Broader影响提出的研究证明复杂性有直接关系的算法可满足性搜索和一般自动推理，任务是人工智能和形式验证的主要工具。 统计物理学和人工智能的研究人员已经提出了随机问题中相变的性质与其相关的计算复杂性之间的强烈联系。PI和其他人最近对证明复杂性的研究揭示了这些领域之间的联系。PI有与统计物理和AI研究人员互动的记录。拟议的研究将继续致力于弥合统计物理学、组合学和理论计算机科学方法之间的差距，并将鼓励思想的相互交流。 通信复杂性是如此重要，以至于它必然会影响计算机科学中的广泛主题。已知技术的影响的列表已经包括从形式验证中使用的OBDD的属性到VLSI布局的效率到数据库系统中的流算法的应用。拟议的研究近似问题的通信复杂性将产生一个机构的结果应用到流算法，并将允许这些概念的扩展，以及图形管道。