Propositional proof systems, the consistency of first order theories and the complexity of computations
From MaRDI portal
Recommendations
Cites work
Cited in
(80)- Frege proof system and TNC°
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
- The problem of proof identity, and why computer scientists should care about Hilbert's 24th problem
- Some consequences of cryptographical conjectures for S 2 1 and EF
- scientific article; zbMATH DE number 517075 (Why is no real title available?)
- On the Power of Substitution in the Calculus of Structures
- Automated Deduction – CADE-20
- INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
- On the complexity of Gödel's proof predicate
- scientific article; zbMATH DE number 7204450 (Why is no real title available?)
- On optimal inverters
- Synthetic Undecidability and Incompleteness of First-Order Axiom Systems in Coq
- Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk)
- Frege proof system and TNC°
- P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
- scientific article; zbMATH DE number 3922641 (Why is no real title available?)
- Optimal proof systems imply complete sets for promise classes
- scientific article; zbMATH DE number 7204319 (Why is no real title available?)
- Combinatorics of first order structures and propositional proof systems
- THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
- The number of proof lines and the size of proofs in first order logic
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- On a generalization of extended resolution
- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
- A note on SAT algorithms and proof complexity
- Further oracles separating conjectures about incompleteness in the finite domain
- Extension without cut
- Reduction of Hilbert-type proof systems to the if-then-else equational logic
- Tautologies from pseudo-random generators
- Proof systems that take advice
- The deduction theorem for strong propositional proof systems
- Substitution and Propositional Proof Complexity
- Speedup for natural problems and noncomputability
- European Summer Meeting of the Association for Symbolic Logic (Logic Colloquium '88), Padova, 1988
- Consistency and optimality
- On an optimal randomized acceptor for graph nonisomorphism
- Propositional proof systems and fast consistency provers
- Propositional representation of arithmetic proofs (preliminary version)
- A Parameterized Halting Problem
- Classes of representable disjoint \textsf{NP}-pairs
- Towards NP-P via proof complexity and search
- Nondeterministic Instance Complexity and Proof Systems with Advice
- The Deduction Theorem for Strong Propositional Proof Systems
- On first-order theorem proving using generalized odd-superpositions II
- On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
- On deciding the truth of certain statements involving the notion of consistency
- Optimal heuristic algorithms for the image of an injective function
- Refutational theorem proving for hierarchic first-order theories
- Computer runtimes and the length of proofs. With an algorithmic probabilistic application to waiting times in automatic theorem proving
- On reducibility and symmetry of disjoint NP pairs.
- Does Advice Help to Prove Propositional Tautologies?
- NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
- Proof complexity of non-classical logics
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Incompleteness in the finite domain
- Some remarks on lengths of propositional proofs
- On an optimal propositional proof system and the structure of easy subsets of TAUT.
- Propositional consistency proofs
- Tuples of disjoint \(\mathsf{NP}\)-sets
- Implicit proofs
- Propositional proof complexity
- scientific article; zbMATH DE number 1354137 (Why is no real title available?)
- Propositional truth maintenance systems: Classification and complexity analysis
- The Complexity of Propositional Proofs
- Consistency, optimality, and incompleteness
- scientific article; zbMATH DE number 4004177 (Why is no real title available?)
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- scientific article; zbMATH DE number 4033740 (Why is no real title available?)
- ALOGTIME and a conjecture of S. A. Cook
- Do there exist complete sets for promise classes?
- On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP
- The symmetry rule in propositional logic
- Logical Closure Properties of Propositional Proof Systems
- Functional interpretations of feasibly constructive arithmetic
- Hardness assumptions in the foundations of theoretical computer science
- Total nondeterministic Turing machines and a p-optimal proof system for SAT
- An oracle separating conjectures about incompleteness in the finite domain
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Nondeterministic functions and the existence of optimal proof systems
- Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
This page was built for publication: Propositional proof systems, the consistency of first order theories and the complexity of computations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3472096)
