权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

RUI: Randomness, Computability, and Complexity in Groups

RUI：组中的随机性、可计算性和复杂性

基本信息

批准号：
2054558
负责人：
Meng-Che Ho
金额：
$ 21万
依托单位：
The University Corporation, Northridge
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2054558&HistoricalAwards=false
关键词：
RUI Randomness Computability Complexity Groups

项目摘要

Groups are a class of fundamental objects in algebra, and more generally, mathematics. They originated as a way to describe symmetries in both mathematics and nature. It turns out that almost all algebraic mathematical structures can be considered as a group with some extra structure. More recently, group theory has also found uses in cryptography. Many tools from other fields, like combinatorics and geometry, have proven useful in the study of groups. Furthermore, group theory has a long history of interaction with logic. In the early developments of logic, group theory was an important testing ground for ideas in logic. On the other hand, it became gradually clear that many ideas from logic were also useful in the study of groups. This project aims to explore this connection and applies tools from logic to advance our understanding of various important classes of groups. This project also provides opportunities and support for students at California State University, Northridge to engage in research in logic and group theory.This project aims to understand the model-theoretic, computability, and complexity properties of groups, and use this understanding to make progress in classifying the finitely-generated groups. The project contains three main parts. The first part aims to analyze the model-theoretic properties of random groups, especially the 0-1 conjecture of first-order sentences in Gromov's random group model. The main tool is the theory developed by Sela, and independently by Kharlampovich and Myasnikov, which they used to solve the 70-year-old Tarski's problem. The second part aims to understand the complexity of describing the elements and multiplication of groups. This includes analyzing the word problem and representative systems of groups using the framework of formal language theory. The third part builds on previous work of the investigator and aims to understand the descriptive complexity of groups, and how they connect to various important classes of finitely-generated groups. More broadly, this part aims to understand the complexity of classes of groups and the relations on them, especially isomorphism, within the context of computability theory. Overall, the project is conducive for student research as it contains many concrete and experimental examples, and will provide training and research experience for the diverse students at California State University, Northridge.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

群是代数乃至数学中的一类基本对象。它们起源于描述数学和自然中对称性的一种方式。事实证明，几乎所有代数数学结构都可以被视为具有一些额外结构的群。最近，群论也在密码学中得到了应用。其他领域的许多工具，如组合学和几何学，已被证明在群的研究中很有用。此外，群论与逻辑的相互作用有着悠久的历史。在逻辑的早期发展中，群论是逻辑思想的重要试验场。另一方面，人们逐渐清楚，许多逻辑思想在群体研究中也很有用。该项目旨在探索这种联系，并应用逻辑工具来增进我们对各种重要群体类别的理解。该项目还为加州州立大学北岭分校的学生从事逻辑和群论研究提供机会和支持。该项目旨在了解群的模型理论、可计算性和复杂性属性，并利用这种理解在有限生成群的分类方面取得进展。该项目包含三个主要部分。第一部分旨在分析随机群的模型理论性质，特别是格罗莫夫随机群模型中一阶句子的0-1猜想。主要工具是塞拉（Sela）以及哈尔拉姆波维奇（Kharlampovich）和米亚斯尼科夫（Myasnikov）独立开发的理论，他们用该理论解决了70岁的塔斯基问题。第二部分旨在理解描述元素和群乘法的复杂性。这包括使用形式语言理论的框架来分析单词问题和群体的代表系统。第三部分建立在研究者之前的工作的基础上，旨在理解群的描述复杂性，以及它们如何与有限生成群的各种重要类别联系起来。更广泛地说，这部分旨在在可计算性理论的背景下理解群类的复杂性及其关系，特别是同构。总体而言，该项目有利于学生研究，因为它包含许多具体的实验实例，并将为加州州立大学北岭分校的多元化学生提供培训和研究经验。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。