Coherence and Computational Complexity of Quantifier-free Dependence Logic Formulas
Tóm tắt
We study the computational complexity of the model checking problem for quantifier-free dependence logic
$${(\mathcal{D})}$$
formulas. We characterize three thresholds in the complexity: logarithmic space (LOGSPACE), non-deterministic logarithmic space (NL) and non-deterministic polynomial time (NP).
Tài liệu tham khảo
Fagin, Ronald, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, in R. Karp (ed.), Complexity of Computation, SIAM-AMS Proceedings 7, 1974, pp. 27–41.
Grädel, E., P. G. Kolaitis, and L. Libkin, Finite Model Theory And Its Applications, Springer, 2007.
Karp, R.M., Reducibility Among Combinatorial Problems, in R.E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, New York: Plenum, 1972, pp. 85–103.
Kontinen, Juha, and Jouko Väänänen, On Definability in Dependence logic, Journal of Logic, Language and Information, Volume 18, Nro. 3, 2009.
Papadimitriou, C. H., Computational Complexity, Addison Wesley, 1993.
Väänänen, Jouko, Dependence Logic: A New Approach to Independence Friendly Logic, Cambridge University Press, 2007.