Instance Compression

实例压缩

• 批准号: 0829754
• 负责人: Lance Fortnow
• 金额: $ 30万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-15 至 2013-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0829754&HistoricalAwards=false
• 关键词: Instance; Compression

Can one efficiently compress search problems with small witnesses into problems whose size depends on the length of the instances? Recent results have given strong negative evidence, for example, that one cannot efficiently map the problem of finding a clique of size k to a problem of size polynomial in k. These question has surprising applications to parameterized complexity, cryptography, probabilistic proof systems and structural complexity.This project will look to extend these results to a number of different directions including showing similar results for probabilistic compression which seem to require new breakthroughs in pseudorandom generators. Also can ever compress a function f that depends on m instances of an NP problem of size n to a single instance of size polynomial in n where the AND function seems to be the major barrier. Finally this project will explore new applications of this line of research as well as other related topics in computational complexity.While this proposal takes a theoretical approach to instance compression, in the long-term continued research in complexity will help focus efforts when trying to tackle difficult computational problems that arise in practice. This project explore these problems with graduate students as part of their thesis research. Research from this project will be desseminated through conference and invited presentations and publications in conferences, journals and on the Internet.

一个有效地压缩搜索问题与小证人的问题，其大小取决于实例的长度？最近的结果给出了强有力的负面证据，例如，人们不能有效地将找到大小为k的团的问题映射为k中的大小多项式的问题。 这些问题在参数化复杂性、密码学、概率证明系统和结构复杂性等方面有着令人惊讶的应用。本项目将把这些结果扩展到许多不同的方向，包括在概率压缩方面显示类似的结果，这似乎需要伪随机生成器的新突破。也可以将依赖于大小为n的NP问题的m个实例的函数f压缩为大小为n的多项式的单个实例，其中AND函数似乎是主要障碍。最后，本项目将探索这一研究领域的新应用以及计算复杂性的其他相关主题。虽然本项目对实例压缩采取了理论方法，但从长远来看，对复杂性的持续研究将有助于在尝试解决实践中出现的困难计算问题时集中精力。本计画将与研究生探讨这些问题，作为他们论文研究的一部分。该项目的研究将通过会议和邀请演讲以及在会议、期刊和互联网上发表论文来进行。