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 Serie 8 75 (1983), fasc. n.3-4, p. 99-101, (English)
pdf (287 Kb), djvu (128 Kb). | MR 0780809 | Zbl 0568.03019
Sunto
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.
Referenze Bibliografiche
[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[9]
Pratt V. (
1975) -
Every prime has a succinct certificate,
«SIAM J. Computing»,
4, 214-220. |
MR 391574 |
Zbl 0316.68031[11]
Slisenko A.O. (
1981) -
Complexity problems in computational theory,
«Russian Math. Surveys»,
36, 23-125. |
MR 643069 |
Zbl 0501.68013
Con il contributo del Ministero per i Beni e le Attività Culturali