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): 8, Downloads (12 Months): 67, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

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.