2021 Student Research Conference:
34th Annual Student Research Conference

Case-by-Case Analysis of the Spectrum Problem: A Proposed Study

Tyler Beauregard
Dr. Todd Palumbo, Faculty Mentor

The spectrum problem proposed by Scholz in 1952 asks whether the family of first-order spectra can be characterized. While many partial answers to this question arose over subsequent years, the first real answer was given separately by R. Fagin and by Jones and Selman. After the groundbreaking results of Fagin and of Jones and Selman in the 1970s, which established the connection between the Scholz's spectrum problem and complexity theory, focus in the field of finite model theory shifted towards similar results.We propose a study looking at alternative ways to address the spectrum problem through the lens of a case-by-case analysis of specific families of sets. We review preliminary research we've completed towards this goal and outline an arithmetic construction of first-order spectra. From this we hope to establish a characterization of certain families of sets as spectra.

Keywords: Logic, Complexity Theory, Model Theory, Spectrum, P vs. NP

Computer Science

Presentation Type: Asynchronous Virtual Oral Presentation

Session: 14-4
Location: https://flipgrid.com/7622b4b3
Time: 0:00

Add to Custom Schedule

Contact SRC Webmaster  |  SRC Privacy Policy