Title: Every super-polynomial proof in purely implicational minimal logic has a polynomially sized proof in classical implicational propositional logic
Abstract: In this article we show how any formula A with a proof in minimal implicational logic that is super-polynomially sized has a polynomially-sized proof in classical implicational propositional logic . This fact provides an argument in favor that any classical propositional tautology has short proofs, i.e., NP=CoNP.
Publication Year: 2015
Publication Date: 2015-05-25
Language: en
Type: preprint
Access and Citation
Cited By Count: 3
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot