Propositional proof complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Propositional proof complexity

Full text

Pdf (25 KB)

Source

Journal of the ACM (JACM) archive
Volume 50 , Issue 1 (January 2003) table of contents

Pages: 80 - 82

Year of Publication: 2003

ISSN:0004-5411

Author

Alexander Razborov

Institute for Advanced Study, Princeton, New Jersey, and Steklov Mathematical Institute, Moscow, Russia

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 57, Citation Count: 0

Additional Information:

references index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/602382.602406 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Beame, P., and Pitassi, T. 1998. Propositional proof complexity: Past, present and future. Tech. Rep. TR98-067, Electronic Colloquium on Computational Complexity.
	2	Maria Luisa Bonet , Toniann Pitassi , Ran Raz, On Interpolation and Automatization for Frege Systems, SIAM Journal on Computing, v.29 n.6, p.1939-1967, April 2000 [doi>10.1137/S0097539798353230]
	3	Cook, S. A., and Reckhow, A. R. 1979. The relative efficiency of propositional proof systems. J. Symb. Logic 44, 1, 36--50.
	4	Jan Krajíček, Bounded arithmetic, propositional logic, and complexity theory, Cambridge University Press, New York, NY, 1996
	5	Pudlák, P. 1998. The lengths of proofs. In Handbook of Proof Theory, S. Buss, Ed. Elsevier, Amsterdam, The Netherlands, 547--637.
	6	Alexander A. Razborov, Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.48-62, July 08-12, 1996
	7	Razborov, A. 2002. Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution. Manuscript in preparation, to be available at http://www.genesis.mi.ras.ru/˜razborov.
	8	Urquhart, A. 1995. The complexity of propositional proofs. Bull. Symb. Logic 1, 425--467.

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.3 Complexity Measures and Classes

Additional Classification:
F. Theory of Computation
F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
F.4.1 Mathematical Logic
Subjects: Proof theory

General Terms:
Theory, Verification

Collaborative Colleagues:

Alexander Razborov: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein

Adobe Acrobat

QuickTime

Windows Media Player

Real Player