On NP coNP proof complexity generators

DOI10.46298/LMCS-22(2:14)2026MaRDI QIDQ7254993zbMATH OpenFDO

Authors Jan Krajíček

Publication date 29 May 2026

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.46298/LMCS-22(2:14)2026

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A limitation on the KPT interpolation
• Bounded arithmetic and the polynomial hierarchy
• scientific article; zbMATH DE number 4213452 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 3557241 (Why is no real title available?)
• scientific article; zbMATH DE number 1354169 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• Proof Complexity
• Proof complexity generators
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The relative efficiency of propositional proof systems
• The strength of replacement in weak arithmetic

This page was built for publication: On \(\mathrm{NP} \cap \mathrm{coNP}\) proof complexity generators

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