Complexicity theory, algorithms and applications

复杂性理论、算法与应用

• 批准号: 386548-2010
• 负责人: Braverman, Mark
• 金额: $ 2.78万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2012
• 资助国家: 加拿大
• 起止时间: 2012-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=508382
• 关键词: Complexicity; theory; algorithms; applications

My current and future research covers a broad range of topics in Theoretical Computer Science as well as applications to Economics and Medicine. My primary area of theoretical research is complexity theory, which explores the amount of computational resources required to perform various tasks. Complexity theory complements algorithm design in mapping out the limitations of computational techniques. I have resolved several long-standing open problems in that area. I am also planning to continue my program on understanding the role computability plays in real-life physical systems by making further progress on the Computability in Dynamics program I have initiated during my PhD studies.

我目前和未来的研究涵盖了理论计算机科学以及经济学和医学应用的广泛主题。我的主要理论研究领域是复杂性理论，它探索执行各种任务所需的计算资源量。复杂性理论补充了算法设计中的计算技术的局限性。我已经解决了这方面几个长期悬而未决的问题。我还计划继续我的程序，了解可计算性在现实生活中的物理系统中发挥的作用，通过在动力学程序的可计算性上取得进一步的进展，我已经开始在我的博士研究。