Optimal proof systems for propositional logic and complete sets

DOI10.1007/BFB0028583MaRDI QIDQ4381398zbMATH OpenFDO

Authors Jochen Messner, Jacobo Torán

Publication date 20 July 1998

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

Full work available at URL https://doi.org/10.1007/BFB0028583

zbMATH Keywords

complexity classesdeterministicexponential timemany-one complete languagesmany-one complete setsnondeterministicp-optimal proof systemsp-simulationpolynomial time

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Optimal proof systems imply complete sets for promise classes
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• scientific article; zbMATH DE number 2080216
• On optimal algorithms and optimal proof systems

Cited in

(26)

• The rue theorem-proving system: The complete set of LIM+ challenge problems
• Optimal proof systems imply complete sets for promise classes
• Reduction of Hilbert-type proof systems to the if-then-else equational logic
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• Hardness and optimality in QBF proof systems modulo NP
• Complete proof systems for weighted modal logic
• A brief proof of the full completeness of Shin's Venn diagram proof system
• A Parameterized Halting Problem
• Do there exist complete sets for promise classes?
• Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
• Logic of Proofs and Labels with a Complete Set of Operations
• Proof Systems for Effectively Propositional Logic
• Optimal acceptors and optimal proof systems
• On slicewise monotone parameterized problems and optimal proof systems for TAUT
• On p-optimal proof systems and logics for PTIME
• scientific article; zbMATH DE number 1335888 (Why is no real title available?)
• scientific article; zbMATH DE number 2080216 (Why is no real title available?)
• scientific article; zbMATH DE number 1500532 (Why is no real title available?)
• scientific article; zbMATH DE number 1738671 (Why is no real title available?)
• scientific article; zbMATH DE number 1929970 (Why is no real title available?)
• OPTIMAL PROOFS OF DETERMINACY II
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
• scientific article; zbMATH DE number 5201477 (Why is no real title available?)
• Proof systems that take advice
• scientific article; zbMATH DE number 7652671 (Why is no real title available?)
• Nondeterministic functions and the existence of optimal proof systems

This page was built for publication: Optimal proof systems for propositional logic and complete sets

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