×

Complexity, decidability and completeness. (English) Zbl 1118.03029

The authors study the “feasible content” of the completeness theorem. It is well known that every computable consistent theory of propositional logic has a computable consistent complete extension. The authors show that if we look at a polynomial-time version of this result, then the analog becomes presentation dependent, along the lines of their earlier work in algebraic structures (such as [Ann. Pure Appl. Logic 56, 313–363 (1992; Zbl 0764.03015)], and many other papers in their program). Thus, every polynomial-time consistent theory of propositional logic has a complete consistent extension in EXPTIME, but there is an NP-time decidable consistent theory of propositional logic with no polynomial-time consistent complete extension if standard binary representation is used. Other results regarding tally sets are proven, and relationships with trees investigated, as are more expressive logics such as predicate logic.

MSC:

03D15 Complexity of computation (including implicit computational complexity)
03B25 Decidability of theories and sets of sentences
03C35 Categoricity and completeness of theories
03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures

Citations:

Zbl 0764.03015
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Feasible mathematics 9 pp 293– (1990)
[2] Classical recursion theory (1989)
[3] Proceedings of structure in complexity, second annual conference pp 218– (1987)
[4] DOI: 10.1007/3-540-60178-3_91 · doi:10.1007/3-540-60178-3_91
[5] Feasible mathematics II 13 pp 91– (1995)
[6] DOI: 10.1002/malq.19950410305 · Zbl 0827.03037 · doi:10.1002/malq.19950410305
[7] DOI: 10.1016/0165-4896(92)90059-E · Zbl 0786.90103 · doi:10.1016/0165-4896(92)90059-E
[8] DOI: 10.1016/0168-0072(92)90076-C · Zbl 0764.03015 · doi:10.1016/0168-0072(92)90076-C
[9] DOI: 10.1016/0168-0072(91)90008-A · Zbl 0756.03021 · doi:10.1016/0168-0072(91)90008-A
[10] Computability theory, Oberwolfach 1996 94 pp 21– (1998)
[11] DOI: 10.1145/321941.321944 · Zbl 0324.65018 · doi:10.1145/321941.321944
[12] Complexity theory of real functions (1991)
[13] Transactions of the American Mathematical Society 173 pp 33– (1972) · Zbl 0247.00014
[14] Formal languages and their relations to automata (1969)
[15] Handbook of recursive mathematics 1 pp 3– (1998)
[16] Every recursive linear ordering has a copy in DTIME(n) 55 pp 260– (1990) · Zbl 0708.03015
[17] Complexity of logical theories 718 (1979)
[18] Bulletin de l’Academie Polonaise des Sciences. Série des Sciences Mathématiques, Astronomiques et Physiques 9 pp 17– (1961)
[19] Finite model theory (1995)
[20] Handbook of recursive mathematics, Vol. 2: Recursive algebra, analysis and combinatorics 139 pp 623– (1998)
[21] DOI: 10.1016/S0049-237X(98)80011-6 · doi:10.1016/S0049-237X(98)80011-6
[22] Recursively enumerable sets and degrees (1987)
[23] Degrees of models 25 pp 233– (1960)
[24] Logical methods 12 pp 321– (1993)
[25] Feasible mathematics 9 pp 321– (1990)
[26] Computational complexity (1994) · Zbl 0833.68049
[27] DOI: 10.1016/0168-0072(89)90047-X · Zbl 0703.03023 · doi:10.1016/0168-0072(89)90047-X
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.