On p-optimal proof systems and logics for PTIME

DOI10.1007/978-3-642-14162-1_27MaRDI QIDQ3587449zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Jörg Flum

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14162-1_27

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1136087
• Total nondeterministic Turing machines and a p-optimal proof system for SAT
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• scientific article; zbMATH DE number 1304339
• On slicewise monotone parameterized problems and optimal proof systems for TAUT

Cited in

(8)

• Hard Instances of Algorithms and Proof Systems
• A Parameterized Halting Problem
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
• A surprising relationship between descriptive complexity and proof complexity
• On slicewise monotone parameterized problems and optimal proof systems for TAUT
• scientific article; zbMATH DE number 1424054 (Why is no real title available?)
• scientific article; zbMATH DE number 5201477 (Why is no real title available?)
• DLOGTIME proof systems

This page was built for publication: On \(p\)-optimal proof systems and logics for PTIME

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