Propositional proof systems, the consistency of first order theories and the complexity of computations
From MaRDI portal
Publication:3472096
DOI10.2307/2274765zbMath0696.03029OpenAlexW2171353564WikidataQ106785096 ScholiaQ106785096MaRDI QIDQ3472096
Publication date: 1989
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2274765
Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Classical propositional logic (03B05) Turing machines and related notions (03D10) Complexity of proofs (03F20)
Related Items
Nondeterministic functions and the existence of optimal proof systems, On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP, A Parameterized Halting Problem, ALOGTIME and a conjecture of S. A. Cook, Hardness assumptions in the foundations of theoretical computer science, Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds, Implicit proofs, Some remarks on lengths of propositional proofs, ON OPTIMAL INVERTERS, INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH, European Summer Meeting of the Association for Symbolic Logic (Logic Colloquium '88), Padova, 1988, Some consequences of cryptographical conjectures for \(S_2^1\) and EF, Classes of representable disjoint \textsf{NP}-pairs, On the Power of Substitution in the Calculus of Structures, NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN, Some consequences of cryptographical conjectures for S 2 1 and EF, Logical Closure Properties of Propositional Proof Systems, Speedup for natural problems and noncomputability, Optimal proof systems imply complete sets for promise classes, Towards NP-P via proof complexity and search, On an optimal randomized acceptor for graph nonisomorphism, On reducibility and symmetry of disjoint NP pairs., Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution, Optimal heuristic algorithms for the image of an injective function, A note on SAT algorithms and proof complexity, Further oracles separating conjectures about incompleteness in the finite domain, On a generalization of extended resolution, The symmetry rule in propositional logic, Reduction of Hilbert-type proof systems to the if-then-else equational logic, A Tight Karp-Lipton Collapse Result in Bounded Arithmetic, Tuples of disjoint \(\mathsf{NP}\)-sets, Propositional consistency proofs, INCOMPLETENESS IN THE FINITE DOMAIN, Tautologies from Pseudo-Random Generators, Functional interpretations of feasibly constructive arithmetic, On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography, Total nondeterministic Turing machines and a p-optimal proof system for SAT, Proof systems that take advice, Extension without cut, The deduction theorem for strong propositional proof systems, The Complexity of Propositional Proofs, The problem of proof identity, and why computer scientists should care about Hilbert's 24th problem, An oracle separating conjectures about incompleteness in the finite domain, Nondeterministic Instance Complexity and Proof Systems with Advice, The Deduction Theorem for Strong Propositional Proof Systems, On the correspondence between arithmetic theories and propositional proof systems – a survey, Unnamed Item, Proof Complexity of Non-classical Logics, Propositional proof complexity, THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS, Does Advice Help to Prove Propositional Tautologies?, Consistency and Optimality, Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes, ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION, P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle, Do there exist complete sets for promise classes?, Frege proof system and TNC°, Frege proof system and TNC°, On an optimal propositional proof system and the structure of easy subsets of TAUT., Substitution and Propositional Proof Complexity
Cites Work
