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