×

The computational complexity of asymptotic problems. I: Partial orders. (English) Zbl 0665.03028

The class of partial orders is shown to have 0-1 laws for first-order logic and for inductive fixed-point logic, a logic which properly contains first-order logic. This means that for every sentence in one of these logics the proportion of labeled (or unlabeled) partial orders of size n satisfying the sentence has a limit of either 0 or 1 as n goes to \(\infty\). This limit, called the asymptotic probability of the sentence, is the same for labeled and unlabeled structures. The computational complexity of the set of sentences with asymptotic probability 1 is determined. For first-order logic, it is PSPACE-complete. For inductive fixed-point logic, it is EXPTIME-complete.

MSC:

03D15 Complexity of computation (including implicit computational complexity)
03B10 Classical first-order logic
03B48 Probability and inductive logic
06A06 Partial orders, general
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aczel, P., An introduction to inductive definitions, (Barwise, J., Handbook of Mathematical Logic (1977), North-Holland: North-Holland Amsterdam), 739-782
[2] Aho, A.; Ullman, J., Universality of data retrieval languages, (Proceedings, 6th ACM Annu. Symposium on Principles of Programming Languages (1979), Assoc. Comput. Mach: Assoc. Comput. Mach New York), 110-120
[3] Blass, A.; Gurevich, Y.; Kozen, D., A zero-one law for logic with a fixed-point operator, Inform. and Control, 67, 70-90 (1985) · Zbl 0608.68077
[4] Chandra, A.; Kozen, D.; Stockmeyer, L., Alternation, J. Assoc. Comput. Mach., 28, 99-128 (1981) · Zbl 0473.68043
[5] Chang, C. C.; Keisler, H. J., (Model Theory (1973), North-Holland: North-Holland Amsterdam) · Zbl 0276.02032
[6] Fagin, R., Probabilities on finite models, J. Symbolic Logic, 41, 50-58 (1976) · Zbl 0341.02044
[7] Fagin, R., The number of finite relational structures, Discrete Math., 19, 17-21 (1977) · Zbl 0389.05006
[8] Gaifman, H., Concerning mesures in first-order calculi, Israel J. Math., 2, 1-18 (1964) · Zbl 0192.03302
[9] Glebskiĭ, Y. V.; Kogan, D. I.; Liogon’kiĭ, M. I.; Talanov, V. A., Range and degree of realizability of formulas in the restricted predicate calculus, Kibernetika (Kiev), 1969, No. 2, 17-28 (1969), English translation, Cybernetics5, 142-154
[10] Grandjean, E., Complexity of the first-order theory of almost all finite structures, Inform. and Control, 57, 180-204 (1983) · Zbl 0542.03018
[11] Gurevich, Y., Toward logic tailored for computational complexity, (Richter, M. M.; etal., Computation and Proof Theory. Computation and Proof Theory, Lecture Notes in Math., Vol. 1104 (1984), Springer-Verlag: Springer-Verlag New York), 175-216
[12] Gurevich, Y.; Shelah, S., Fixed-point extensions of first-order logic, (Proceedings, 26th Annu. IEEE Symposium on Foundations of Computer Science (1985)), 346-353
[13] Immerman, N., Relational queries computable in polynomial time, Inform. and Control, 68, 86-104 (1986) · Zbl 0612.68086
[14] Kaufmann, M.; Shelah, S., On random models of finite power and monadic logic, Discrete Math., 54, 285-293 (1983) · Zbl 0579.03006
[15] Kim, K. H., (Boolean Matrix Theory and Applications (1982), Dekker: Dekker New York)
[16] Kleitman, D. J.; Rothschild, B. L., Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205, 205-220 (1975) · Zbl 0302.05007
[17] Knuth, D. E., (The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0302.68010
[18] Liogon’kiĭ, M. I., On the question of quantitative characteristics of logical formulas, Kibernetika (Kiev), 1970, No. 3, 16-22 (1970), English translation, Cybernetics6, 205-211 · Zbl 0229.02040
[19] Lynch, J. F., Almost sure theories, Ann. Math. Logic, 18, 91-135 (1980) · Zbl 0433.03020
[20] Möhring, R., Problem 1.6, (Rival, I., Graphs and Order (1985), Reidel: Reidel Dordrecht), 524
[21] Moschovakis, Y. N., (Elementary Induction on Abstract Structures (1974), North-Holland: North-Holland Amsterdam) · Zbl 0307.02003
[22] Moschovakis, Y. N., On non-monotone inductive definability, Fund. Math., 82, 39-83 (1974) · Zbl 0306.02039
[23] Oberschelp, W., Strukturzahlen in endlichen relationssystemen, (Schmidt, H. A.; etal., Logic Colloquium 1966 (1968), North-Holland: North-Holland Amsterdam) · Zbl 0216.30602
[24] Prömel, H. J., Counting unlabeled structures, J. Combin. Theory Ser. A, 44, 83-93 (1987) · Zbl 0618.05029
[25] Stockmeyer, L., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[26] Vardi, M., Complexity of relational query languages, (14th Annu. ACM Symposium on Theory of Computing (1982)), 137-146
[27] Winkler, P., Random orders, Order, 1, 317-331 (1985) · Zbl 0565.06002
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.