scientific article; zbMATH DE number 3557241
From MaRDI portal
Publication:4133141
Cited in
(74)- Propositional consistency proofs
- Bounded arithmetic and the polynomial hierarchy
- Bounded linear logic: A modular approach to polynomial-time computability
- A new recursion-theoretic characterization of the polytime functions
- Intuitionistic propositional logic is polynomial-space complete
- The complexity of Gentzen systems for propositional logic
- Bounded arithmetic, proof complexity and two papers of Parikh
- ALOGTIME and a conjecture of S. A. Cook
- On parallel hierarchies and R_k^i
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Resolution and binary decision diagrams cannot simulate each other polynomially
- A second-order system for polytime reasoning based on Grädel's theorem.
- Theories with self-application and computational complexity.
- Short proofs of the Kneser-Lovász coloring principle
- Automated higher-order complexity analysis
- The proof complexity of linear algebra
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Unprovability of consistency statements in fragments of bounded arithmetic
- A bounded arithmetic AID for Frege systems
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Expander construction in \(\mathrm{VNC}^1\)
- The canonical pairs of bounded depth Frege systems
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Induction rules in bounded arithmetic
- Hardness assumptions in the foundations of theoretical computer science
- Logics for reasoning about cryptographic constructions
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Unprovability of circuit upper bounds in Cook's theory PV
- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
- Logical Closure Properties of Propositional Proof Systems
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Dynamic Symmetry Breaking by Simulating Zykov Contraction
- Towards NP-P via proof complexity and search
- A note on SAT algorithms and proof complexity
- Strict finitism, feasibility, and the sorites
- Expander construction in \(\mathsf{VNC}^1\)
- Incompleteness in the finite domain
- Circuit lower bounds in bounded arithmetics
- Consistency proof of a fragment of PV with substitution in bounded arithmetic
- DRAT and propagation redundancy proofs without new variables
- Substitution and Propositional Proof Complexity
- Approximate counting and NP search problems
- INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
- A remark on pseudo proof systems and hard instances of the satisfiability problem
- The NP search problems of Frege and extended Frege proofs
- On the complexity of cutting-plane proofs
- On feasible numbers
- Some consequences of cryptographical conjectures for S 2 1 and EF
- Frege proof system and TNC°
- Models of Bounded Arithmetic Theories and Some Related Complexity Questions
- Mining the surface: witnessing the low complexity theorems of arithmetic
- The provably total NP search problems of weak second order bounded arithmetic
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Unprovability of strong complexity lower bounds in bounded arithmetic
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Constructive separations and their consequences
- Complexity barriers as independence
- First-order reasoning and efficient semi-algebraic proofs
- Witnessing flows in arithmetic
- Tractability of cut-free Gentzen type propositional calculus with permutation inference
- Enumerating error bounded polytime algorithms through arithmetical theories
- Functional interpretations of feasibly constructive arithmetic
- Succinct PPRFs via memory-tight reductions
- The strength of the dominance rule
- From proof complexity to circuit complexity via interactive protocols
- A proof complexity conjecture and the incompleteness theorem
- On proving consistency of equational theories in bounded arithmetic
- Feasibility of primality in bounded arithmetic
- Prime factorization in models of \(\mathrm{PV}_1\)
- On \(\mathrm{NP} \cap \mathrm{coNP}\) proof complexity generators
- Towards PNP from extended Frege lower bounds
- On the complexity of finding falsifying assignments for Herbrand disjunctions
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 Q4133141)
