Fixed dimension polynomial time

Speaker(s)

Mikołaj Bojańczyk (joint work with Szymon Toruńczyk)

Affiliation

Uniwersytet Warszawski

Date

March 6, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

We describe a complexity class for sets with atoms, which contains problems on orbit-finite inputs like graph reachability, emptiness and minimisation for automata.
The idea is that the algorithm must be polynomial for inputs that have fixed dimension.
Dimension is a parameter that is similar to the number of registers in a register automaton.
 

---