IEEE - Institute of Electrical and Electronics Engineers, Inc. - No feasible interpolation for TC/sup 0/-Frege proofs

Proceedings 38th Annual Symposium on Foundations of Computer Science

Author(s): Bonet, M.L. ; Pitassi, T. ; Raz, R.
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 January 1997
Conference Location: Miami Beach, FL, USA, USA
Conference Date: 20 October 1997
Page(s): 254 - 263
ISBN (Paper): 0-8186-8197-7
ISSN (Paper): 0272-5428
DOI: 10.1109/SFCS.1997.646114
Regular:

The interpolation method has been one of the main tools for proving lower bounds for propositional proof systems. Loosely speaking, if one can prove that a particular proof system has the feasible... View More

Advertisement