Generalizing Nondeterminism for Computational Machines Over Algebraic Structures

Wednesday, May 8, 2013 at 1:00pm to 1:45pm

Bronfman Science Center, 106 18 Hoxsey St, Williamstown, MA 01267, USA

Generalizing Nondeterminism for Computational Machines Over Algebraic Structures

Scott Sanderson '13

Mathematics and Statistics Department Thesis Defense

Abstract: 

We present an introduction to the BSS Machine model of complexity
theory, which generalizes the classical Turing Machine model by
allowing for computation over uncountably infinite algebraic
structures.  Building on the BSS model, we present a novel
characterization—which naturally generalizes the classical
nondeterministic Turing Machine—of the complexity class NP over
a ring R, and we present results relating our class to alternative
formulations of NP.

Share
Subscribe
Event Type

lecture/seminar/presentation

Department

Mathematics & Statistics

Recent Activity

People Going

Getting Here