Previous |  Up |  Next


Title: Speed-up for propositional Frege systems via generalizations of proofs (English)
Author: Krajíček, Jan
Language: English
Journal: Commentationes Mathematicae Universitatis Carolinae
ISSN: 0010-2628 (print)
ISSN: 1213-7243 (online)
Volume: 30
Issue: 1
Year: 1989
Pages: 137-140
Category: math
MSC: 03B05
MSC: 03F07
MSC: 03F20
idZBL: Zbl 0675.03034
idMR: MR995712
Date available: 2008-06-05T21:37:06Z
Last updated: 2012-04-28
Stable URL:
Reference: [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 0469688
Reference: [2] S. A. Cook R. A. Reckhow: The relative efficiency of propositional proof systems.J. Symb. Logic 44 (1979), 36-50. MR 0523487
Reference: [3] M. Dowd: Model-theoretic aspects of $P ≠ NP$.preprint (1985).
Reference: [4] W. F. Farmer: Length of proofs and unification theory.Ph.D. thesis, Univ. of Wisconsin-Madison, 1984.
Reference: [5] J. Krajíček: On the number of steps in appear in Annals of Pure and Applied Logic. MR 0983000
Reference: [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 0955313
Reference: [7] J. Krajíček P. Pudlák: Propositional proof systems, the consistency of first order theories and the complexity of appear in J. Symbolic Logic. MR 1011192
Reference: [8] R. Parikh: Some results on the length of proofs.Trans. Amer. Math. Soc. 117 (1973), 29-36. Zbl 0269.02011, MR 0432416


Files Size Format View
CommentatMathUnivCarol_030-1989-1_17.pdf 401.6Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo