On Universality of Regular Realizability Problems

We prove the universality of the regular realizability problem for several classes of filters. These filters are descriptions of finite relations on the set of nonnegative integers in the format proposed by P. Wolf and H. Fernau. The universality is proved with respect to the disjunctive reduction in polynomial time for unary relations and in polynomial space for invariant binary relations. The necessity of stronger reductions corresponds to the results of Wolf and Fernau on the decidability of regular realizability problems for many algorithmic problems in graph theory.