Δ -tautologies, uniform and non-uniform upper bounds in computation theory

Daniele Mundici

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni (1983)

  • Volume: 75, Issue: 3-4, page 99-101
  • ISSN: 1120-6330

How to cite

top

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 Lincei. Matematica e Applicazioni 75.3-4 (1983): 99-101. <http://eudml.org/doc/287238>.

@article{Mundici1983,
author = {Mundici, Daniele},
journal = {Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni},
keywords = {tautologies with one interpolant; sentential interpolants; circuit depth; nondeterministic Turing time; proof length; complexity of the decision problem},
language = {eng},
month = {9},
number = {3-4},
pages = {99-101},
publisher = {Accademia Nazionale dei Lincei},
title = {$\Delta$-tautologies, uniform and non-uniform upper bounds in computation theory},
url = {http://eudml.org/doc/287238},
volume = {75},
year = {1983},
}

TY - JOUR
AU - Mundici, Daniele
TI - $\Delta$-tautologies, uniform and non-uniform upper bounds in computation theory
JO - Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni
DA - 1983/9//
PB - Accademia Nazionale dei Lincei
VL - 75
IS - 3-4
SP - 99
EP - 101
LA - eng
KW - tautologies with one interpolant; sentential interpolants; circuit depth; nondeterministic Turing time; proof length; complexity of the decision problem
UR - http://eudml.org/doc/287238
ER -

References

top
  1. Chang, C.C. and Keisler, H.J. (1977) - Model Theory. North-Holland, Amsterdam, second edition. MR532927
  2. Feferman, S. (1974) — Applications of many-sorted interpolation theorems. In: Proceedings Tarski Symposium, «AMS Proc. Symp. Pure Math.», 25, 205-223. Zbl0311.02060MR406772
  3. Machtey, M. and Young, P. (1979) - An Introduction to the General Theory of Algorithms. North-Holland, Amsterdam, third printing. Zbl0376.68027MR483344
  4. Manders, K.L. (1980) - Computational complexity of decision problems in elementary number theory, Springer «Lecture Notes in Mathematics», 834, 211-227. Zbl0444.03019MR606788
  5. Miller, G.L. (1976) — Riemann's hypothesis and tests for primality, «Journal of Computer and System Sciences», 13, 300-317. Zbl0349.68025MR480295
  6. Mundici, D. (1984) - NP and Craig's interpolation theorem. In: Logic Colloquium 1982, North-Holland, Amsterdam, to appear. Zbl0594.03021MR762116DOI10.1016/S0049-237X(08)71822-6
  7. Mundici, D. (1984) - Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity, submitted for publication. Zbl0594.03022MR765593DOI10.1016/0168-0072(84)90029-0
  8. Mundici, D. (1983) - A lower bound for the complexity of Craig's interpolants in sentential logic, «Archiv math. Logik», 23, 27-36. Zbl0511.03004MR710362DOI10.1007/BF02023010
  9. Pratt, V. (1975) - Every prime has a succinct certificate, «SIAM J. Computing», 4, 214-220. Zbl0316.68031MR391574
  10. Savage, J.E. (1976) - The Complexity of Computing. Wiley, New York. Zbl0391.68025MR495205
  11. Slisenko, A.O. (1981) - Complexity problems in computational theory, «Russian Math. Surveys», 36, 23-125. Zbl0501.68013MR643069

NotesEmbed ?

top

You must be logged in to post comments.