| 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:
|
http://hdl.handle.net/10338.dmlcz/106714 |
| . |
| 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 proofs.to 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 computations.to 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 |
| . |
