The reachability query is of particular interest for investigating the expressive power of DynFO, since is one the simplest queries that cannot be expressed statically in first-order logic, but rather requires recursion. We introduce a theory of Dynamic Complexity using notation from descriptive complexity. We study the class DynFO by showing which problems are in DynFO and the relation between DynFO and other classes as P, P-complete, L- complete, Nl-complete and DynAC$^{0}$. We also defined "bounded-expansion reductions" which honor dynamic complexity classes. Then we give a detailed proof of Reachability being in DynFO by using computational linear algebra problems. Futhermore, using the previous result and techniques from its proof, we prove that 2-Sat is DynFO and PerfectMatching and MaxMatching are in non-uniform DynFO.
Name
Stavros Taxiarchis Potsakis
Date of Defense
09-06-2021
Three-member Committee
Archontia Giannopoulou
Dimitrios Thilikos
Stathis Zachos (Advisor)
Abstract