scientific article; zbMATH DE number 5845490
From MaRDI portal
Publication:3072543
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Models of arithmetic and set theory (03C62) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Recommendations
- Logical Approaches to Computational Barriers
- Higher randomness and forcing with closed sets
- Higher randomness and forcing with closed sets
- Forcing. An introduction to the mathematics of independence proofs
- On sufficient conditions for unsatisfiability of random formulas
- Forcing in Proof Theory
- Namba forcing, weak approximation, and guessing
- Pseudorandom Generators in Propositional Proof Complexity
- Provability with Finitely Many Variables
- Forcing and the Halpern-Läuchli theorem
Cited in
(26)- A saturation property of structures obtained by forcing with a compact family of random variables
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Partially definable forcing and bounded arithmetic
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Zero knowledge and circuit minimization
- Typical forcings, NP search problems and an extension of a theorem of Riis
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10
- Feasible interpolation for QBF resolution calculi
- Towards NP-P via proof complexity and search
- Characterizing propositional proofs as noncommutative formulas
- Proof Complexity
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- The Complexity of Propositional Proofs
- INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
- scientific article; zbMATH DE number 7561750 (Why is no real title available?)
- NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
- A remark on pseudo proof systems and hard instances of the satisfiability problem
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- Consistency of circuit evaluation, extended resolution and total NP search problems
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
- Extended Nullstellensatz proof systems
- On the consistency of circuit lower bounds for non-deterministic time
- Learning algorithms from circuit lower bounds
- Towards PNP from extended Frege lower bounds
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3072543)
