×

Succinctness as a source of complexity in logical formalisms. (English) Zbl 0933.03048

Summary: The often observed complexity gap between the expressiveness of a logical formalism and its exponentially harder expression complexity is proven for all logical formalisms which satisfy natural closure conditions. The expression complexity of the prefix classes of second-order logic can thus be located in the corresponding classes of the weak exponential hierarchies; further results about expression complexity in database theory, logic programming, nonmonotonic reasoning, first-order logic with Henkin quantifiers and default logic are concluded. The proof method illustrates the significance of quantifier-free interpretations in descriptive complexity theory.

MSC:

03D15 Complexity of computation (including implicit computational complexity)
03C13 Model theory of finite structures
03C85 Second- and higher-order model theory
68Q19 Descriptive complexity and finite models

Software:

Datalog
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balcázar, J., The complexity of searching implicit graphs, (22nd ICALP. 22nd ICALP, Lecture Notes in Computer Science, vol. 944 (1995), Springer: Springer Berlin), 209-219
[2] Balcázar, J.; Lozano, A.; Toran, J., The complexity of algorithmic problems on succinct instances, (Baeza-Yates, R.; Manber, U., Computer Science (1992), Plenum Press: Plenum Press New York), 351-377
[3] Blass, A.; Gurevich, Y., Henkin quantifiers and complete problems, Ann. Pure Appl. Logic, 32, 1-16 (1986) · Zbl 0618.03016
[4] Borchert, B.; Lozano, A., Succinct circuit representations and leaf languages are basically the same concept, Inform. Process. Lett., 58, 211-215 (1996) · Zbl 0875.68429
[5] Borchert, B.; Silvestri, R., A characterization of the leaf language classes, Inform. Process. Lett., 63, 153-158 (1997) · Zbl 1337.68110
[6] Cadoli, M.; Eiter, T.; Gottlob, G., Using default logic as a query language, IEEE Trans. Knowledge Data Eng., 9, 3, 448-463 (1997)
[7] Chandra, A.; Kozen, C.; Stockmeyer, L., Alternation, J. Assoc. Comput. Mach., 28, 114-133 (1981) · Zbl 0473.68043
[8] Compton, K.; Henson, C., A uniform method for proving lower bounds on the computational complexity of logical theories, Ann. Pure Appl. Logic, 48, 1-79 (1990) · Zbl 0705.03017
[9] Ebbinghaus, H.; Flum, J., Finite Model Theory (1995), Springer: Springer Berlin
[10] Eiter, T.; Gottlob, G., The complexity of logic-based abduction, J. Assoc. Comput. Mach., 42, 1, 3-42 (1995) · Zbl 0886.68121
[11] Eiter, T.; Gottlob, G.; Leone, N., Abduction from logic programs: semantics and complexity, (Theoretical Computer Science — Logic, Semantics and Theory of programming, vol. 189 (1997), Elsevier: Elsevier Amsterdam), 129-177 · Zbl 0893.68022
[12] Eiter, T.; Gottlob, G.; Mannila, H., Disjunctive datalog, ACM Trans. Database Systems, 22, 364-418 (1997)
[13] Eiter, T.; Leone, N.; Sacca, D., Expressive power and complexity of partial models for disjunctive deductive databases, (Theoretical Computer Science — Logic, Semantics and Theory of programming, vol. 206 (1998), Elsevier: Elsevier Amsterdam), 181-218 · Zbl 0913.68053
[14] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, (Karp, R. M., Complexity of Computation (1974)), 43-74
[15] Galperin, H.; Wigderson, A., Succinct representation of graphs, Inform. Control, 56, 183-198 (1983) · Zbl 0538.68053
[16] Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[17] Gottlob, G., Complexity results for nonmonotonic logics, J. Logic Comput., 2, 3, 397-425 (1992) · Zbl 0765.03012
[18] Gottlob, G., Relativized logspace and generalized quantifiers over finite structures, J. Symbolic Logic, 62, 2, 545-574 (1997) · Zbl 0882.03031
[19] Gottlob, G.; Leone, N.; Veith, H., Second order logic and the weak exponential hierarchies, (Mathematical Foundations of Computer Science (MFCS). Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science, vol. 969 (1995), Springer: Springer Berlin), 66-81 · Zbl 1193.68115
[20] Hanf, W., Model-theoretic methods in the study of elementary logic, (Addison, J.; Henkin, L.; Tarski, A., The Theory of Models (1965), North-Holland: North-Holland Amsterdam), 132-145 · Zbl 0166.25801
[21] Hartmanis, J.; Immerman, N.; Sewelson, V., Sparse sets in NP-Pol: EXPTIME versus NEXPTIME, Inform. Control, 65, 159-181 (1985) · Zbl 0586.68042
[22] Hartmanis, J.; Stearns, R. E., On the computational complexity of algorithms, Trans. Am. Math. Soc., 117, 285-306 (1965) · Zbl 0131.15404
[23] Hartmanis, J.; Yesha, Y., Computation times of NP sets of different densities, Theoret. Comp. Sci., 34, 17-32 (1984) · Zbl 0985.68515
[24] Hemachandra, L. A., The strong exponential hierarchy collapses, J. Comput. System Sci., 39, 299-322 (1989) · Zbl 0693.03022
[25] Henkin, L., Some remarks on infinitely long formulas, (Symp. on the Foundations of Mathematics. Symp. on the Foundations of Mathematics, Warsaw (1959)), 167-183 · Zbl 0121.25308
[26] Hobbs, J.; Stickel, M., Interpretation as abduction, (26th Annual Meeting of the Assoc. for Computational Linguistics (1988))
[27] Immerman, N., Languages that capture complexity classes, SIAM J. Comput., 16, 760-778 (1987) · Zbl 0634.68034
[28] Immerman, N., Nondeterministic space is closed under complementation, SIAM J. Comput., 17, 935-938 (1988) · Zbl 0668.68056
[29] Johnson, D., A catalog of complexity classes, (Leeuwen, van, Handbook of Theoretical Computer Science (1990), Elsevier: Elsevier Amsterdam), 67-162 · Zbl 0900.68246
[30] Kakas, A.; Mancarella, P., Generalized stable models: a semantics for abduction, ((1989), ECAI), 385-391
[31] Kakas, A.; Mancarella, P., Database updates through abduction, ((1990), VLDB), 650-661
[32] Kolaitis, P.; Papadimitriou, C., Why not negation by fixpoint?, J. Comput. System Sci., 43, 125-144 (1991) · Zbl 0753.68028
[33] Krynicki, M.; Mostowski, M., Henkin quantifiers, (M. K.; etal., Quantifiers: Logics, Models and Computation, vol. 1 (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 193-262 · Zbl 0904.03023
[34] Ladner, R.; Lynch, N., Relativizations about questions of logspace computability, J. Comput. System Sci., 10, 19-32 (1976) · Zbl 0341.68036
[35] Papadimitriou, C., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0833.68049
[36] Papadimitriou, C.; Yannakakis, M., A note on succinct representations of graphs, Inform. Control, 71, 181-185 (1985) · Zbl 0616.68041
[37] Peirce, C., Abduction and induction, (Buchler, J., Philosophical Writings of Peirce (1955), Dover: Dover New York), Ch. 11
[38] Poole, D., Normality and faults in logic based diagnosis, ((1989), IJCAI), 1304-1310
[39] Reiter, R., A logic for default reasoning, Artif. Intell., 13, 81-132 (1980) · Zbl 0435.68069
[40] Selman, A., (1st. Structure in Complexity Theory Conference. 1st. Structure in Complexity Theory Conference, Lecture Notes in Computer Science, vol. 223 (1986), Springer: Springer Berlin)
[41] Sher, G., The Bounds of Logic (1991), MIT Press: MIT Press Cambridge
[42] Stewart, I., Complete problems involving boolean labelled structures and projection transactions, J. Logic Comput., 1, 861-882 (1991) · Zbl 0744.03040
[43] Stewart, I., Logical characterization of bounded query classes I: Logspace oracle machines, Fund. Inform., 18, 65-92 (1993) · Zbl 0782.68049
[44] Stewart, I., Logical characterization of bounded query classes II: Logspace oracle machines, Fund. Inform., 18, 93-105 (1993) · Zbl 0782.68050
[45] Stewart, I., On completeness for NP via projection translations, (Lecture Notes in Comput. Sci., vol. 626 (1993), Springer: Springer Berlin), 353-366 · Zbl 0819.68066
[46] Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[47] Szelepcsényi, R., The method of forced enumeration for nondeterministic automata, Acta Inform., 26, 279-284 (1988) · Zbl 0638.68046
[48] Väänänen, J., Remarks on generalized quantifiers and second order logics, Prace Naukowe Inst. Mat. Politech. Wroclawski ser. kon. (1977) · Zbl 0382.03010
[49] Vardi, M., Complexity of relational query languages, (14th Symp. on Theory of Computing (STOC) (1982)), 137-146
[50] Veith, H., How to encode a logical structure as a string, (Technical Report DBAI-TR-97-10 (1997), Institute of Information Systems: Institute of Information Systems TU Vienna) · Zbl 0935.68051
[51] Veith, H., Languages represented by boolean formulas, Inform. Process. Lett., 63, 251-256 (1997) · Zbl 1337.68139
[52] Veith, H., Succinct representation, leaf languages and projection reductions, Inform. Comput., 142, 207-236 (1998) · Zbl 0909.68079
[53] Wagner, K., The complexity of combinatorial problems with succinct input representation, Acta Inform., 23, 325-356 (1986) · Zbl 0621.68032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.