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
Topic(s):Mathematics
Computer Science
Presentation Type: Asynchronous Virtual Oral Presentation
Session: 14-2
Location: https://flipgrid.com/7622b4b3
Time: 0:00