On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP

DOI10.1007/BFb0036203MaRDI QIDQ5055954

Zenon Sadowski

Publication date: 9 December 2022

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Nondeterministic functions and the existence of optimal proof systems ⋮ Optimal proof systems imply complete sets for promise classes

Cites Work

• The polynomial-time hierarchy
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Quantified propositional calculi and fragments of bounded arithmetic
• The relative efficiency of propositional proof systems
• The Complexity of Propositional Proofs
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP