SpringerLink - Book Chapter

Institutional Login

Welcome!

To use the personalized features of this site, please log in or register.

If you have forgotten your username or password, we can help.

My Menu

Marked Items

Alerts

Order History

Saved Items

All

Favorites


Book Chapter

Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus

Book Series	Lecture Notes in Computer Science
Publisher	Springer Berlin / Heidelberg
ISSN	0302-9743 (Print) 1611-3349 (Online)
Volume	Volume 1295/1997
Book	Mathematical Foundations of Computer Science 1997
DOI	10.1007/BFb0029943
Copyright	1997
ISBN	978-3-540-63437-9
Category	Invited Papers
DOI	10.1007/BFb0029951
Pages	85-90
Subject Collection	Computer Science
SpringerLink Date	Monday, April 10, 2006

Add to marked items

Add to shopping cart

Add to saved items

Permissions & Reprints

Recommend this chapter

PDF (404.6 KB)

Free Preview

Invited Papers

Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus

Jan Kraji ccaron ek¹

(1)	Mathematical Institute, University of Oxford, 24-29 St.Giles', OX1 3LB Oxford, UK

Abstract

We prove lower bounds for a proof system having exponential speed-up over both polynomial calculus and constant-depth Frege systems in DeMorgan language.

Partially supported by cooperative research grant INT-9600919/ME-103 from the NSF (USA) and the M Scaron

MT (Czech republic) and by the grant #A1019602 of the Academy of Sciences of the Czech Republic.