Some consequences of cryptographical conjectures for S 2 1 and EF

DOI10.1007/3-540-60178-3_86MaRDI QIDQ6064283

Pavel Pudlák, Jan Krajíček

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

propositional logicinterpolation theoremproof systemdiscrete logarithmtruth assignment

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Cites Work

• Bounded arithmetic and the polynomial hierarchy
• Fragments of Bounded Arithmetic and Bounded Query Classes
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• RSA and Rabin Functions: Certain Parts are as Hard as the Whole
• Every Prime Has a Succinct Certificate
• A method for obtaining digital signatures and public-key cryptosystems
• Lower bounds to the size of constant-depth propositional proofs
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some consequences of cryptographical conjectures for S 2 1 and EF