An Investigation of the Isomporphism Conjecture, Self- Reducibility, and Reverse Mathematics (Pure Mathematics Logic)) and Theoretical Computer Science (Computer Science)

复杂性可以被认为是理论计算机科学的主要基础。它研究的是有限资源下的可计算性。一个在结构复杂性领域激发了大量工作的问题是，在各种约简下，是否所有等价的集合都是多项式同构的。1977年，J. Hartmanis和L.Berman推测所有np完全集合都是多项式同构的。这个问题还没有解决。在大多数困难问题的实例中，构建神谕来决定问题的任何一种方式都是直截了当的。在同构猜想的情况下，这是不正确的。没有已知的神谕可以成立同构猜想。戈德史密斯博士将继续研究同构猜想。她将继续致力于自约性和oracle可访问性。她将通过分析定理陈述的复杂性和使用反向数学证明它们的标准技术来研究复杂性理论中构造的困难。互动活动包括教授入门级的本科课程，其中提供榜样是至关重要的。Goldsmith博士还将参加复杂性理论和逻辑研讨会，并将继续参加东北集合理论研讨会。该项目进一步推进了VPW计划的目标，即(1)为女性提供在工程和NSF支持的科学学科中发展职业的机会；(2)通过为在工业、政府和学术机构工作的女性科学家和工程师提供更大的知名度，鼓励女性在科学和工程领域追求职业。通过鼓励妇女参与科学，这是对国家未来科学活力的宝贵投资。

Complexity can be considered the primary foundation of theoretical computer science. It is the study of computability with limited resources. A problem that has stimulated a large body of work in structural complexity is whether all sets equivalent under various reductions are polynomially isomorhic. In 1977, J. Hartmanis and L.Berman conjectured that all NP-complete sets are polynomially isomorphic. This is still open. In most instances of difficult problems, it has been straightforward to construct oracles to decide the problems either way. In the case of the isomorphism conjecture, this has not been true. There is no known oracle for which the isomorphism conjecture holds. Dr. Goldsmith will continue to investigate the isomorphism conjecture. She will continue working on self-reducibility and oracle accessibility. She will investigate the difficulty of constructions in complexity theory by analyzing the complexity of the statements of the theorems and the standard techniques for proving them, using reverse mathematics. Interactive activities include teaching an undergraduate course at the introductory level where it is crucial that role models be provided. Dr. Goldsmith will also participate in complexity theory and logic seminars and will continue her participation in the Northeastern Set Theory Seminar. This project furthers VPW program objectives which are (1) to provide opportunities for women to advance their careers in engineering and in the disciplines of science supported by NSF and (2) to encourage women to pursue careers in science and engineering by providing greater visibility for women scientists and engineers employed in industry, government, and academic institutions. By encouraging the participation of women in science, it is a valuable investment in the Nation's future scientific vitality.