Paper Info
Title
Optimal Proof Systems for Propositional Logic and Complete Sets
Abstract
A polynomial time computable function h : \Sigma! \Sigmawhose range is the set of tautologiesin Propositional Logic (TAUT), is called a proof system. Cook and Reckhowdefined this concept in [6] and in order to compare the relative strength of differentproof systems, they considered the notion of p-simulation. Intuitively a proof system hp-simulates a second one h0if there is a polynomial time computable function fl translatingproofs in h0into proofs in h. A proof system is ...
Year
DOI
Venue
1997
10.1007/BFb0028583
STACS '98 Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science
Keywords
DocType
Volume
complete sets,optimal proof systems,propositional logic,information content,complexity class,polynomial time
Journal
4
Issue
ISSN
ISBN
26
0302-9743
3-540-64230-7
Citations 
PageRank 
References 
13
0.86
9
Authors
3
Name
Order
Citations
PageRank
Jochen Meßner1131.19
Jacobo Torán256449.26
J Messner3131.19