Publication:4152212

From MaRDI portal
Revision as of 11:24, 6 February 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


zbMath0375.02004MaRDI QIDQ4152212

Robert A. Reckhow, Stephen A. Cook

Publication date: 1974



68Q25: Analysis of algorithms and problem complexity

05A99: Enumerative combinatorics

03B05: Classical propositional logic


Related Items

Characterizing Propositional Proofs as Noncommutative Formulas, Non-elementary speed-ups in proof length by different variants of classical analytic calculi, Proof Complexity Meets Algebra, Witnessing matrix identities and proof complexity, Generalisation of proof simulation procedures for Frege systems by M.L. Bonet and S.R. Buss, Simulation of Natural Deduction and Gentzen Sequent Calculus, The Complexity of Finding Read-Once NAE-Resolution Refutations, Complexity of translations from resolution to sequent calculus, The NP Search Problems of Frege and Extended Frege Proofs, Proof Complexity of Non-classical Logics, Semantics and proof-theory of depth bounded Boolean logics, Logical omniscience as infeasibility, Towards NP-P via proof complexity and search, Practical extraction of evidence terms from common-knowledge reasoning, Extended clause learning, Short propositional refutations for dense random 3CNF formulas, The intractability of resolution, An answer to an open problem of Urquhart, Tautology testing with a generalized matrix reduction method, On the complexity of regular resolution and the Davis-Putnam procedure, The complexity of Gentzen systems for propositional logic, On the relative merits of path dissolution and the method of analytic tableaux, Controlled integration of the cut rule into connection tableau calculi, A proper hierarchy of propositional sequent calculi, Davis-Putnam resolution versus unrestricted resolution, Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, Optimal proof systems imply complete sets for promise classes, Resolution and binary decision diagrams cannot simulate each other polynomially, The proof complexity of analytic and clausal tableaux, Relative efficiency of propositional proof systems: Resolution vs. cut-free LK, Short proofs of the Kneser-Lovász coloring principle, Classical logic, argument and dialectic, Some remarks on lengths of propositional proofs, Resolution remains hard under equivalence, On a generalization of extended resolution, On the complexity of choosing the branching literal in DPLL, Non-circular proofs and proof realization in modal logic, Making knowledge explicit: how hard it is, Frege systems for extensible modal logics, On linear rewriting systems for Boolean logic and some applications to proof theory, Propositional Proofs in Frege and Extended Frege Systems (Abstract), NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability, Satisfiability problems for propositional calculi, A note on some computationally difficult set covering problems