Δ -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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.