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可访问性。她将通过分析定理陈述的复杂性以及使用逆向数学证明它们的标准技术来研究复杂性理论中的构造难度。互动活动包括在入门级教授本科课程，其中提供角色模型至关重要。金匠博士还将参加复杂性理论和逻辑研讨会，并将继续参加东北集理论研讨会。该项目进一步推动了自愿工作妇女方案的目标，即：（1）为妇女提供机会，使她们在工程和国家科学基金会支持的科学学科中取得职业发展;（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.