Meta-Algorithms versus Circuit Lower Bounds

元算法与电路下界

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

计算机戏剧性地改变了我们的生活。我们现在可以有效地解决许多计算问题，这些问题如果没有计算机是不可能解决的。然而，许多重要的问题似乎仍然超出了我们最强大的超级计算机的能力范围。这些问题表面上的困难是真的吗(问题本身)，或者这些问题确实有我们还没有发现的有效的算法解决方案？