The complexity of theorem-proving procedures

Cited in

(only showing first 100 items - show all)

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
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
The complexity of reachability in distributed communicating processes
On the complexity of the maximum satisfiability problem for Horn formulas
Satisfiability in many-valued sentential logic is NP-complete
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
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
A hierarchy of propositional Horn formuls
Uniform data encodings
Complexity of Boolean algebras
Backtracking with multi-level dynamic search rearrangement
Fast probabilistic algorithms for Hamiltonian circuits and matchings
Complexity of dimension three and some related edge-covering characteristics of graphs
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
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 shortest common supersequence problem over binary alphabet is NP- complete
Some simplified undecidable and NP-hard problems for simple programs
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
Reductions on NP and p-selective sets
An NP-complete matching problem
Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
On the zero-inequivalence problem for loop programs
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
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
The membership question for ETOL-languages is polynomially complete
A class of facet producing graphs for vertex packing polyhedra
Boolesche Minimalpolynome und Überdeckungsprobleme
Translational lemmas, polynomial time, and \((\log n)^j\)-space
Comparing complexity classes
Constructing optimal binary decision trees is NP-complete
Some simplified NP-complete graph problems
A lower bound on the number of additions in monotone computations
Relative complexity of checking and evaluating
Complete problems for deterministic polynomial time
The polynomial-time hierarchy
Complexity-class-encoding sets
Sparse complex polynomials and polynomial reducibility
On the complexity of formal grammars
Efficient Algorithms for (3,1) Graphs
Complete sets and the polynomial-time hierarchy
Log space machines with multiple oracle tapes
On polynomial time isomorphisms of some new complete sets
On graphs with Hamiltonian squares
Cyclic ordering is NP-complete
On the complexity of regular resolution and the Davis-Putnam procedure
On log-tape isomorphisms of complete sets
The distribution of 1-widths of (0,1)-matrices
A linear-time algorithm for testing the truth of certain quantified Boolean formulas
Arithmetical hierarchy and complexity of computation
Complexity in mechanized hypothesis formation
Even initial feedback vertex set problem is NP-complete
Testing for existence of a covering Boyce-Codd normal form
On the communication complexity of zero-knowledge proofs
Strong nondeterministic Turing reduction - a technique for proving intractability
A note on the computational complexity of the pure classical implication calculus
Computations on nondeterministic cellular automata
Sentences over integral domains and their computational complexities
A two-phase algorithm for solving a class of hard satisfiability problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5667480)