On p-optimal proof systems and logics for PTIME
From MaRDI portal
Publication:3587449
DOI10.1007/978-3-642-14162-1_27zbMATH Open1288.03031OpenAlexW1712906147MaRDI QIDQ3587449FDOQ3587449
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
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
Model theory of finite structures (03C13) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (8)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Parameterized Halting Problem
- Hard Instances of Algorithms and Proof Systems
- DLOGTIME proof systems
- NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
- On slicewise monotone parameterized problems and optimal proof systems for TAUT
- A surprising relationship between descriptive complexity and proof complexity
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)
