Paper Info
Title
On the Structure of the Simulation Order of Proof Systems
Abstract
We examine the degree structure of the simulation relation on the proof systems for a set L. As observed, this partial order forms a distributive lattice. A greatest element exists iff L has an optimal proof system. In case L is infinite there is no least element, and the class of proof systems for L is not presentable. As we further show the simulation order is dense. In fact any partial order can be embedded into the interval determined by two proof systems f and g such that f simulates g but g does not simulate f. Finally we obtain that for any non-optimal proof system h an infinite set of proof systems that are pairwise incomparable with respect simulation and that are also incomparable to h.
Year
DOI
Venue
2002
10.1007/3-540-45687-2_48
MFCS
Keywords
Field
DocType
optimal proof system,proof systems,non-optimal proof system h,case l,simulation order,greatest element,simulation relation,iff l,respect simulation,partial order,proof system,distributive lattice
Pairwise comparison,Discrete mathematics,Combinatorics,Distributive lattice,Infinite set,Turing machine,Proof complexity,Greatest element,Mathematics
Conference
Volume
ISSN
ISBN
2420
0302-9743
3-540-44040-2
Citations 
PageRank 
References 
1
0.38
8
Authors
1
Name
Order
Citations
PageRank
Jochen Messner1704.86