Geodesic
$\Delta$-tautologies, uniform and non-uniform upper bounds in computation theory
Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali, Série 8, Tome 75 (1983) no. 3-4, pp. 99-101.

Voir la notice de l'article provenant de la source Biblioteca Digitale Italiana di Matematica

Una $\Delta$-tautologia è una tautologia del tipo $H \rightarrow 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. 
@article{RLINA_1983_8_75_3-4_a0,
     author = {Mundici, Daniele},
     title = {$\Delta$-tautologies, uniform and non-uniform upper bounds in computation theory},
     journal = {Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali},
     pages = {99--101},
     publisher = {mathdoc},
     volume = {Ser. 8, 75},
     number = {3-4},
     year = {1983},
     zbl = {0568.03019},
     mrnumber = {0780809},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RLINA_1983_8_75_3-4_a0/}
}
TY  - JOUR
AU  - Mundici, Daniele
TI  - $\Delta$-tautologies, uniform and non-uniform upper bounds in computation theory
JO  - Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali
PY  - 1983
SP  - 99
EP  - 101
VL  - 75
IS  - 3-4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/RLINA_1983_8_75_3-4_a0/
LA  - en
ID  - RLINA_1983_8_75_3-4_a0
ER  - 
%0 Journal Article
%A Mundici, Daniele
%T $\Delta$-tautologies, uniform and non-uniform upper bounds in computation theory
%J Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali
%D 1983
%P 99-101
%V 75
%N 3-4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/RLINA_1983_8_75_3-4_a0/
%G en
%F RLINA_1983_8_75_3-4_a0
Mundici, Daniele. $\Delta$-tautologies, uniform and non-uniform upper bounds in computation theory. Atti della Accademia nazionale dei Lincei. Rendiconti della Classe di scienze fisiche, matematiche e naturali, Série 8, Tome 75 (1983) no. 3-4, pp. 99-101. http://geodesic.mathdoc.fr/item/RLINA_1983_8_75_3-4_a0/

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

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

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

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

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

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

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

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

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

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

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