Fixed dimension polynomial time

Prelegent(ci)

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

Afiliacja

Uniwersytet Warszawski

Termin

6 marca 2019 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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.
 

---