On an optimal propositional proof system and the structure of easy subsets of TAUT.

DOI10.1016/S0304-3975(01)00155-4zbMath1061.03061MaRDI QIDQ1853507

Zenon Sadowski

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Complexity classesClassical propositional logicComplexity of computationComplexity of proofs

Mathematics Subject Classification ID

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

Related Items (13)

Nondeterministic functions and the existence of optimal proof systems ⋮ A Parameterized Halting Problem ⋮ Reductions between disjoint NP-pairs ⋮ ON OPTIMAL INVERTERS ⋮ Logical Closure Properties of Propositional Proof Systems ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ The deduction theorem for strong propositional proof systems ⋮ Hard Instances of Algorithms and Proof Systems ⋮ The Deduction Theorem for Strong Propositional Proof Systems ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Consistency and Optimality ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes ⋮ Do there exist complete sets for promise classes?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity classes without machines: on complete languages for UP
• On the structure of sets in NP and other complexity classes
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The relative efficiency of propositional proof systems
• The complexity of theorem-proving procedures
• Classes of Recursively Enumerable Sets and Their Decision Problems

This page was built for publication: On an optimal propositional proof system and the structure of easy subsets of TAUT.