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