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 难题（例如永久问题）。