Record: found
Abstract: not found
Book Chapter: not found

A bottom-up approach to foundations of mathematics

other

Author(s): Pavel Pudlák

Publication date (Print): 1996

Publisher: Springer Berlin Heidelberg

Read this book at

Publisher

Buy book

Bookmark

There is no author summary for this book yet. Authors can add summaries to their books on ScienceOpen to make them more accessible to a non-specialist audience.

Related collections

Most cited references 27

Record: found
Abstract: found
Article: not found

The relative efficiency of propositional proof systems

Stephen Cook, Robert A. Reckhow (1979)

We are interested in studying the length of the shortest proof of a propositional tautology in various proof systems as a function of the length of the tautology. The smallest upper bound known for this function is exponential, no matter what the proof system. A question we would like to answer (but have not been able to) is whether this function has a polynomial bound for some proof system. (This question is motivated below.) Our results here are relative results.