Geodesic
Speed-up for propositional Frege systems via generalizations of proofs
Commentationes Mathematicae Universitatis Carolinae, Tome 30 (1989) no. 1, pp. 137-140 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 03B05, 03F07, 03F20 
@article{CMUC_1989_30_1_a16,
     author = {Kraj{\'\i}\v{c}ek, Jan},
     title = {Speed-up for propositional {Frege} systems via generalizations of proofs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {137--140},
     year = {1989},
     volume = {30},
     number = {1},
     mrnumber = {995712},
     zbl = {0675.03034},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1989_30_1_a16/}
}
TY  - JOUR
AU  - Krajíček, Jan
TI  - Speed-up for propositional Frege systems via generalizations of proofs
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1989
SP  - 137
EP  - 140
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMUC_1989_30_1_a16/
LA  - en
ID  - CMUC_1989_30_1_a16
ER  - 
%0 Journal Article
%A Krajíček, Jan
%T Speed-up for propositional Frege systems via generalizations of proofs
%J Commentationes Mathematicae Universitatis Carolinae
%D 1989
%P 137-140
%V 30
%N 1
%U http://geodesic.mathdoc.fr/item/CMUC_1989_30_1_a16/
%G en
%F CMUC_1989_30_1_a16
Krajíček, Jan. Speed-up for propositional Frege systems via generalizations of proofs. Commentationes Mathematicae Universitatis Carolinae, Tome 30 (1989) no. 1, pp. 137-140. http://geodesic.mathdoc.fr/item/CMUC_1989_30_1_a16/

[1] 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. | MR

[2] S. A. Cook R. A. Reckhow: The relative efficiency of propositional proof systems. J. Symb. Logic 44 (1979), 36-50. | MR

[3] M. Dowd: Model-theoretic aspects of $P ≠ NP$. preprint (1985).

[4] W. F. Farmer: Length of proofs and unification theory. Ph.D. thesis, Univ. of Wisconsin-Madison, 1984.

[5] J. Krajíček: On the number of steps in proofs. to appear in Annals of Pure and Applied Logic. | MR

[6] 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. | MR

[7] 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. | MR

[8] R. Parikh: Some results on the length of proofs. Trans. Amer. Math. Soc. 117 (1973), 29-36. | MR | Zbl