Meta-Algorithms versus Circuit Lower Bounds

元算法与电路下界

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

计算机极大地改变了我们的生活。我们现在可以有效地解决许多没有计算机就无法解决的计算问题。然而，许多重要的问题似乎仍然超出了我们最强大的超级计算机的能力范围。这些问题的表面难度是否真实（问题的本质），或者这些问题确实有我们尚未发现的有效算法解决方案？