The complexity of theorem-proving procedures

DOI10.1145/800157.805047zbMath0253.68020DBLPconf/stoc/Cook71OpenAlexW2036265926WikidataQ55867257 ScholiaQ55867257MaRDI QIDQ5667480

Stephen A. Cook

Publication date: 1971

Full work available at URL: https://doi.org/10.1145/800157.805047

Mathematics Subject Classification ID

Related Items (only showing first 100 items - show all)

An easily testable optimal-time VLSI-multiplier ⋮ Heuristic evaluation techniques for bin packing approximation algorithms ⋮ A comment on \('NP=P?'\) and restricted partitions ⋮ NP-completeness results concerning greedy and super greedy linear extensions ⋮ An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ Short propositional formulas represent nondeterministic computations ⋮ A comparison of polynomial time completeness notions ⋮ On helping by robust oracle machines ⋮ Masking traveling beams: optical solutions for NP-complete problems, trading space for time ⋮ The complexity of reachability in distributed communicating processes ⋮ Computing equilibria: a computational complexity perspective ⋮ On the complexity of the maximum satisfiability problem for Horn formulas ⋮ Satisfiability in many-valued sentential logic is NP-complete ⋮ Maintenance routing for train units: the interchange model ⋮ Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes ⋮ Analyzing the complexity of finding good neighborhood functions for local search algorithms ⋮ The complexity of optimization problems ⋮ Decompositions of nondeterministic reductions ⋮ Complexity classes without machines: on complete languages for UP ⋮ LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation ⋮ Polynomially solvable satisfiability problems ⋮ Shortest enclosing walks and cycles in embedded graphs ⋮ Computational complexity of some restricted instances of 3-SAT ⋮ A hierarchy of propositional Horn formuls ⋮ Uniform data encodings ⋮ Complexity of Boolean algebras ⋮ Backtracking with multi-level dynamic search rearrangement ⋮ Spectral classes of regular, random, and empirical graphs ⋮ On the complexity of role colouring planar graphs, trees and cographs ⋮ Two-machine interval shop scheduling with time lags ⋮ Fast probabilistic algorithms for Hamiltonian circuits and matchings ⋮ Stream-based inconsistency measurement ⋮ Complexity of dimension three and some related edge-covering characteristics of graphs ⋮ The maximum infection time in the geodesic and monophonic convexities ⋮ Non existence of some mixed Moore graphs of diameter 2 using SAT ⋮ Automatic construction of optimal static sequential portfolios for AI planning and beyond ⋮ Towards a logical belief function theory ⋮ On the complexity of the constrained input selection problem for structural linear systems ⋮ The complexity of the equivalence problem for two characterizations of Presburger sets ⋮ On gamma-reducibility versus polynomial time many-one reducibility ⋮ Non deterministic polynomial optimization problems and their approximations ⋮ Optimization problems and the polynomial hierarchy ⋮ Complexity of graph embeddability problems ⋮ Probabilistic satisfiability: algorithms with the presence and absence of a phase transition ⋮ A switching algorithm for the solution of quadratic Boolean equations ⋮ Complexity of algorithms and computations ⋮ On the size of refutation Kripke models for some linear modal and tense logics ⋮ The number of depth-first searches of an ordered set ⋮ The shortest common supersequence problem over binary alphabet is NP- complete ⋮ Some simplified undecidable and NP-hard problems for simple programs ⋮ Complexity-theoretic algebra. II: Boolean algebras ⋮ On the complexity of simple arithmetic expressions ⋮ Some results on relativized deterministic and nondeterministic time hierarchies ⋮ On the structure of sets in NP and other complexity classes ⋮ A uniform approach to obtain diagonal sets in complexity classes ⋮ An effective structured approach to finding optimal partitions of networks ⋮ A note on sparse oracles for NP ⋮ On the relationship between the biconnectivity augmentation and traveling salesman problems ⋮ A state-of-the-art review of parallel-machine scheduling research ⋮ Reductions on NP and p-selective sets ⋮ On the complexity of ranking ⋮ Probabilistic bounds and algorithms for the maximum satisfiability problem ⋮ An NP-complete matching problem ⋮ Modelling and simulation of communications network planning ⋮ Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis ⋮ An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\)) ⋮ On the zero-inequivalence problem for loop programs ⋮ Scatter search and genetic algorithms for MAX-SAT problems ⋮ New complexity results about Nash equilibria ⋮ Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs ⋮ New updating criteria for conflict-based branching heuristics in DPLL algorithms for satisfiability ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Unrestricted resolution versus N-resolution ⋮ A bounded approximation for the minimum cost 2-sat problem ⋮ On polynomial-time Turing and many-one completeness in PSPACE ⋮ The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory ⋮ George Dantzig's impact on the theory of computation ⋮ Complexity results for three-dimensional orthogonal graph drawing ⋮ A pseudo-Boolean consensus approach to nonlinear 0-1 optimization ⋮ A note on the permanent value problem ⋮ A simple proof of a theorem of Statman ⋮ On the computational complexity of integral equations ⋮ A hierarchy of tractable satisfiability problems ⋮ Decision-making coordination and efficient reasoning techniques for feature-based configuration ⋮ Alternating states for dual nondeterminism in imperative programming ⋮ The membership question for ETOL-languages is polynomially complete ⋮ The deduction theorem for strong propositional proof systems ⋮ Complexity classes for self-assembling flexible tiles ⋮ On the inapproximability of independent domination in \(2P_3\)-free perfect graphs ⋮ Hybrid commitments and their applications to zero-knowledge proof systems ⋮ Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT ⋮ On problems without polynomial kernels ⋮ Cryptography with constant input locality ⋮ On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls ⋮ The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions ⋮ On the computation of the hull number of a graph ⋮ APX-hardness of domination problems in circle graphs ⋮ Strong nondeterministic polynomial-time reducibilities ⋮ On some natural complete operators ⋮ Complete problems in the first-order predicate calculus

This page was built for publication: The complexity of theorem-proving procedures