Δ-tautologies, uniform and non-uniform upper bounds in computation theory
Mundici, Daniele
Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti, Tome 74 (1983), p. 99-101 / Harvested from Biblioteca Digitale Italiana di Matematica
Access to full text
Full (PDF)
Full (DjVu)

Una Δ-tautologia è una tautologia del tipo H→K avente un solo interpolante di Craig J, a meno di equivalenza logica. Utilizzando misure di complessità relative al problema di trovare tale J, mostriamo come si possano ottenere limiti non uniformi di complessità mediante limiti uniformi, e viceversa.

Publié le : 1983-09-01
@article{RLINA_1983_8_75_3-4_99_0,
     author = {Daniele Mundici},
     title = {$\Delta$-tautologies, uniform and non-uniform upper bounds in computation theory},
     journal = {Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti},
     volume = {74},
     year = {1983},
     pages = {99-101},
     zbl = {0568.03019},
     mrnumber = {0780809},
     language = {en},
     url = {http://dml.mathdoc.fr/item/RLINA_1983_8_75_3-4_99_0}
}

Mundici, Daniele. $\Delta$-tautologies, uniform and non-uniform upper bounds in computation theory. Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti, Tome 74 (1983) pp. 99-101. http://gdmltest.u-ga.fr/item/RLINA_1983_8_75_3-4_99_0/

[1] Chang, C.C. and Keisler, H.J. (1977) - Model Theory. North-Holland, Amsterdam, second edition. | MR 532927

[2] Feferman, S. (1974) — Applications of many-sorted interpolation theorems. In: Proceedings Tarski Symposium, «AMS Proc. Symp. Pure Math.», 25, 205-223. | MR 406772 | Zbl 0311.02060

[3] Machtey, M. and Young, P. (1979) - An Introduction to the General Theory of Algorithms. North-Holland, Amsterdam, third printing. | MR 483344 | Zbl 0376.68027

[4] Manders, K.L. (1980) - Computational complexity of decision problems in elementary number theory, Springer «Lecture Notes in Mathematics», 834, 211-227. | MR 606788 | Zbl 0444.03019

[5] Miller, G.L. (1976) — Riemann's hypothesis and tests for primality, «Journal of Computer and System Sciences», 13, 300-317. | MR 480295 | Zbl 0349.68025

[6] Mundici, D. (1984) - NP and Craig's interpolation theorem. In: Logic Colloquium 1982, North-Holland, Amsterdam, to appear. | MR 762116 | Zbl 0594.03021

[7] Mundici, D. (1984) - Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity, submitted for publication. | MR 765593 | Zbl 0594.03022

[8] Mundici, D. (1983) - A lower bound for the complexity of Craig's interpolants in sentential logic, «Archiv math. Logik», 23, 27-36. | MR 710362 | Zbl 0511.03004

[9] Pratt, V. (1975) - Every prime has a succinct certificate, «SIAM J. Computing», 4, 214-220. | MR 391574 | Zbl 0316.68031

[10] Savage, J.E. (1976) - The Complexity of Computing. Wiley, New York. | MR 495205 | Zbl 0391.68025

[11] Slisenko, A.O. (1981) - Complexity problems in computational theory, «Russian Math. Surveys», 36, 23-125. | MR 643069 | Zbl 0501.68013