Computability and Complexity in Mathematics

数学中的可计算性和复杂性

• 批准号: 1363310
• 负责人: Antonio Montalban
• 金额: $ 20万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-15 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1363310&HistoricalAwards=false
• 关键词: Computability; Complexity; Mathematics

Antonio Montalban will study problems in Computability Theory. He is interested in the interplay between complexity and mathematics. In mathematics, as we all know, some structures are more complicated than others, some constructions more complicated than others, and some proofs more complicated than others. He plans to apply methods from computability theory to study the complexity of various areas of both classical mathematics and foundations of mathematics.One of our objectives is to study of the computational properties of counterexamples to Vaught's conjecture, which is one of the most well-known and longest-standing conjectures in logic. This is with an eye towards either showing that those counterexamples do not exist, or just trying to understand them if they do exist. Montalban has already shown that being a counterexample to Vaught's conjecture is equivalent to a couple of purely computability-theoretic properties, and he has in mind a few other properties that might also end up being equivalent.

安东尼奥·蒙塔尔班（Antonio Montalban）将研究计算理论中的问题。他对复杂性和数学之间的相互作用感兴趣。众所周知，在数学中，某些结构比其他结构更复杂，有些结构比其他结构更复杂，有些结构比其他结构更复杂。他计划应用计算理论中的方法来研究经典数学和数学基础的各个领域的复杂性。我们的目标之一是研究反例的计算特性，即Vaught的猜想，这是逻辑中最著名，最长时间的猜想之一。这是指向表明这些反例不存在的，或者只是试图理解它们是否存在。蒙塔尔班已经表明，作为Vaught的猜想的反例，相当于几个纯粹的可计算性理论属性，并且他还要牢记其他一些属性，这些属性也可能最终是等效的。