Time-Space Lower Bounds for NP-Hard Problems

NP 难问题的时空下界

• 批准号: 0728809
• 负责人: Dieter van Melkebeek
• 金额: $ 27万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-01-01 至 2010-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728809&HistoricalAwards=false
• 关键词: Time; Space; Lower; Bounds; NP

This project studies the intrinsic power and limitations of current and future computing devices. The focus lies on so-called NP-complete problems, a ubiquitous class of computational problems and the subject of one of the seven millennium prize questions proposed by the Clay Mathematics Institute as grand challenges for the 21st century. No efficient algorithms for NP-complete problems are known. Such algorithms would have many applications in science and engineering but would also jeopardize the security of internet communication. In fact, all the cryptographic systems currently in use hinge on the assumption that there do not exist efficient algorithms for NP-complete problems. The goal of this research is to make progress in establishing that premise by showing that NP-complete problems do not have efficient algorithms that use a small amount of memory space.The investigator and other authors have shown that satisfiability does not have a deterministic algorithm that runs in time n^c and space n^d for certain nontrivial combinations of the constants c and d. The same holds for other natural NP-complete problems. This project intends to quantitatively improve the time-space lower bounds for NP-complete problems in the deterministic model. A concrete objective for satisfiability is a quadratic time lower bound for subpolynomial-space algorithms. The project also aims to establish similar lower bounds in the randomized and the quantum model, where currently nothing nontrivial is known. An ambitious long-term goal is to prove superpolynomial lower bounds for subpolynomial-space algorithms that solve more complex NP-hard problems like the permanent.

本项目研究当前和未来计算设备的内在能力和局限性。 重点在于所谓的NP完全问题，一个无处不在的计算问题和克莱数学研究所提出的21世纪世纪重大挑战的七个千年奖问题之一的主题。 没有有效的算法NP完全问题是已知的。 这种算法在科学和工程领域有许多应用，但也会危及互联网通信的安全。 事实上，目前使用的所有密码系统都基于这样一个假设，即不存在解决NP完全问题的有效算法。 本研究的目标是通过证明NP完全问题不存在使用少量内存空间的有效算法来建立这一前提。研究者和其他作者已经证明了可满足性不存在一个确定性算法，该算法对于常数c和d的某些非平凡组合在时间n^c和空间n^d中运行。 这同样适用于其他自然NP完全问题。 本计画的目的是在确定性模型中，对NP完全问题的时空下界进行量化的改进。 可满足性的一个具体目标是子多项式空间算法的二次时间下界。 该项目还旨在在随机和量子模型中建立类似的下限，目前还没有任何非平凡的东西。 一个雄心勃勃的长期目标是证明子多项式空间算法的超多项式下界，以解决更复杂的NP-难问题，如永久性。