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

点击翻译按钮获取中文摘要

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.