Complete problems for dynamic complexity classes
Proceedings - Symposium on Logic in Computer Science - Trang 313-322
Tóm tắt
We present the first complete problems for dynamic complexity classes including the classes Dyn-FO and Dyn-ThC/sup 0/, the dynamic classes corresponding to relational calculus and (polynomially bounded) SQL, respectively. The first problem we show complete for Dyn-FO is a single-step version of the circuit value problem (SSCV). Of independent interest, our construction also produces a first-order formula, /spl zeta/, that is in a sense universal for all first-order formulas. Since first-order formulas are stratified by quantifier depth, the first-order formula /spl zeta/ emulates formulas of greater depth by iterated application. As a corollary we obtain a fixed quantifier block, QBC, that is complete for all first-order quantifier blocks.
Từ khóa
#Polynomials #Computer science #Complexity theory #Databases #Heuristic algorithms #Data structures #Logic #Calculus #Circuits #Application softwareTài liệu tham khảo
hesse, 2001, The dynamic complexity of transitive closure is in TC0, Intl Conf on Database Theory, 234
10.1006/inco.1995.1102
barrington, 1990, On uniformity within NC1, JCSS, 41, 274
10.1016/0304-3975(94)90159-7
libkin, 1999, On the Power of Incremental Evaluation in SQL-Like Languages
jagadish, 1998, View maintenance issues for the chronicle data model, Materialized Views Techniques Implementations and Applications, 241
10.1007/978-1-4612-0539-5
10.1145/800061.808733
10.1006/jcss.1997.1520