Publication:4152212
From MaRDI portal
zbMath0375.02004MaRDI QIDQ4152212
Stephen A. Cook, Robert A. Reckhow
Publication date: 1974
68Q25: Analysis of algorithms and problem complexity
05A99: Enumerative combinatorics
03B05: Classical propositional logic
Related Items
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, 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, 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, Making knowledge explicit: how hard it is, Frege systems for extensible modal logics, Satisfiability problems for propositional calculi, A note on some computationally difficult set covering problems
