On the structure of the simulation order of proof systems

DOI10.1007/3-540-45687-2_48MaRDI QIDQ4708605zbMATH OpenFDO

Authors Jochen Messner

Publication date 18 June 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2420/24200581.htm

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• Optimal proof systems for propositional logic and complete sets
• On a P-optimal proof system for the set of all satisfiable Boolean formulas (SAT)
• Optimal proof systems imply complete sets for promise classes
• Optimal proof systems and sparse sets
• On the relative efficiency of different systems for classical and nonclassical propositional logics

Cited in

(5)

• Simulation preorder over simple process algebras
• Monotone simulations of non-monotone proofs.
• On an optimal randomized acceptor for graph nonisomorphism
• Hard instances of algorithms and proof systems
• Canonical disjoint NP-pairs of propositional proof systems

This page was built for publication: On the structure of the simulation order of proof systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4708605)