Daniel Spiegel (CU Boulder Physics) Algebraic Quantum Field Theory à la Haag-Kastler
Wed, Mar. 18 3pm (Zoom)
Join at https://cuboulder.zoom.us/j/511481743
We investigate the computational complexity of checking whether a finite semigroup given by generators has certain properties. We are concerned specifically with transformation semigroups, matrix semigroups, and partial bijection semigroups. Some key results include: (1) checking that a transformation semigroup is a group is in AC^0, (2) checking if a transformation semigroup satisfies a fixed equation is in NL, (3) checking whether an element is regular in a transformation semigroup is PSPACE-complete, (4) checking that a matrix is nilpotent is in P, and (5) checking membership in a partial bijection semigroup is PSPACE-complete.
Computational Complexity of Semigroup Properties
CANCELED Wed, Mar. 18
Grad Student Seminar
Levi Lorenzo (CU Boulder)
Given a polynomial f, the orbit of zero under f creates a dynamical sequence (0,f(0),f^2(0), ...). Given a sequence (a_n), a natural question to ask is: when does n divide a_n? , For reasons we will discuss, this question is especially nice to ask for such "dynamically generated" sequences, but even in such sequences, is not nicely answered in general. How does the so-called "divisibility set" depend on the degree of the polynomial? How does it depend on the constant term? What happens if we allow non-integer rational coefficients and examine the numerators of such a sequence? What if we work over a different number field?
Index Divisibility in Dynamically Generated Sequences