You are not logged in |
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.
