Meta-Algorithms versus Circuit Lower Bounds

元算法与电路下界

• 批准号: 298363-2012
• 负责人: Kabanets, Valentine
• 金额: $ 2.48万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=571486
• 关键词: Meta; Algorithms; versus; Circuit; Lower

Computers have dramatically changed our lives. We can now efficiently solve many computational problems that would be impossible to solve without computers. Yet, many important problems still seem beyond the reach of even our most powerful super-computers. Is the apparent difficulty of these problems real (intrinsic to the problem), or these problems do have efficient algorithmic solutions that we haven't been able to discover yet? The field of computational complexity studies precisely this question: what problems require excessive computational resources (computation time, memory, etc.)? In addition to clarifying the boundary of what can be solved efficiently, identifying computationally hard problems also has important practical consequences. For instance, the security of virtually all cryptographic systems in use today (including electronic banking) relies on the unproven assumptions that certain computational problems are very hard to solve. Thus, proving that such problems are actually hard would prove that these cryptographic protocols are truly secure. One of important discoveries of modern complexity theory is the deep connection between proving the hardness of computational problems and designing efficient algorithms for related computational problems. The two tasks are like Ying and Yang of Computer Science: progress in one is impossible without progress in the other. The main goal of the proposed research is to gain better insight into this connection, and exploit it to make further progress in both computational hardness and efficient algorithm design.

计算机已经极大地改变了我们的生活。现在，我们可以有效地解决许多计算机问题，而没有计算机就无法解决。然而，即使是我们最强大的超级计算机，许多重要的问题似乎仍然无法实现。这些问题的明显困难是真实的（问题上的固有），还是这些问题确实具有我们尚未发现的有效算法解决方案？ 计算复杂性研究的领域准确是此问题：哪些问题需要过多的计算资源（计算时间，内存等）？除了阐明可以有效解决的边界之外，识别计算困难问题还具有重要的实际后果。例如，几乎所有正在使用的加密系统（包括电子银行）的安全性取决于未经证实的假设，即某些计算问题很难解决。因此，证明这些问题实际上很难证明这些加密协议确实是安全的。 现代复杂性理论的重要发现之一是深厚的联系 在证明计算问题的硬度和为相关计算问题设计有效的算法之间。这两个任务就像计算机科学的Ying和Yang：一个不可能的进步是不可能的。 拟议的研究的主要目标是更好地了解这种联系，并利用它以在计算硬度和有效算法设计方面取得进一步的进步。