Nie jesteś zalogowany |
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.
