# Speed-up for propositional Frege systems via generalizations of proofs

Commentationes Mathematicae Universitatis Carolinae (1989)

- Volume: 030, Issue: 1, page 137-140
- ISSN: 0010-2628

## Access Full Article

top## How to cite

topKrajíček, Jan. "Speed-up for propositional Frege systems via generalizations of proofs." Commentationes Mathematicae Universitatis Carolinae 030.1 (1989): 137-140. <http://eudml.org/doc/17708>.

@article{Krajíček1989,

author = {Krajíček, Jan},

journal = {Commentationes Mathematicae Universitatis Carolinae},

keywords = {Frege system; speed-up},

language = {eng},

number = {1},

pages = {137-140},

publisher = {Charles University in Prague, Faculty of Mathematics and Physics},

title = {Speed-up for propositional Frege systems via generalizations of proofs},

url = {http://eudml.org/doc/17708},

volume = {030},

year = {1989},

}

TY - JOUR

AU - Krajíček, Jan

TI - Speed-up for propositional Frege systems via generalizations of proofs

JO - Commentationes Mathematicae Universitatis Carolinae

PY - 1989

PB - Charles University in Prague, Faculty of Mathematics and Physics

VL - 030

IS - 1

SP - 137

EP - 140

LA - eng

KW - Frege system; speed-up

UR - http://eudml.org/doc/17708

ER -

## References

top- G. C. Cejtin A. A. Čubarjan, On some bounds to the lengths of logical proofs in classical propositional calculus, (Russian), Truudy Vyčisl. Centra AN ArmSSR i Erevan. univ. 8 (1975), 57-64. (1975) MR0469688
- S. A. Cook R. A. Reckhow, The relative efficiency of propositional proof systems, J. Symb. Logic 44 (1979), 36-50. (1979) Zbl0408.03044MR0523487
- M. Dowd, Model-theoretic aspects of $P\ne NP$, preprint (1985). (1985)
- W. F. Farmer, Length of proofs and unification theory, Ph.D. thesis, Univ. of Wisconsin-Madison, 1984. (1984)
- J. Krajíček, On the number of steps in proofs, to appear in Annals of Pure and Applied Logic. Zbl0672.03042MR0983000
- J. Krajíček P. Pudlák, The number of proof lines and the size of proofs in first order logic, Archive for Mathematical Logic 27 (1988), 69-84. (1988) Zbl0644.03032MR0955313
- J. Krajíček P. Pudlák, Propositional proof systems, the consistency of first order theories and the complexity of computations, to appear in J. Symbolic Logic. Zbl0696.03029MR1011192
- R. Parikh, Some results on the length of proofs, Trans. Amer. Math. Soc. 117 (1973), 29-36. (1973) Zbl0269.02011MR0432416

## NotesEmbed ?

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