判定有限自动机可重置的二次多项式下界OA北大核心CSTPCD

The time lower bounds of deciding resettable finite automata problem and road coloring problem were studied.It is proved that the lower bounds of these two problems are quadratic polynomials about the number of automata states and the number of vertices of directed graph,respectively.This shows that under exponential time hypothesis(ETH)the existing quadratic algorithms for both problems are almost the theoretically best.For the former problem,the fine-grained reduction from the intersection of two finite automata problem to it is established,and with transitivity of fine-grained reduction it is proved that the lower bound of determining whether the finite automaton is resettable or not is a quadratic polynomial about the number of the states.For the latter,because solving a certain problem is at least as hard as verifying one of its solutions,the proof regards deciding whether an automaton is resettable or not as verifying a solution of road coloring problem,and then it is proved that the lower bound of road coloring problem is a quadratic polynomial about the number of vertices.