The complexity of theorem-proving procedures

Cited in

(only showing first 100 items - show all)

The time complexity of permutation routing via matching, token swapping and a variant
Approximating the minimum hub cover problem on planar graphs
A decomposition method for CNF minimality proofs
A pseudo-Boolean consensus approach to nonlinear 0-1 optimization
Some modifications of auxiliary pushdown automata
Boolesche Minimalpolynome und Überdeckungsprobleme
Physical consequences of \(P \neq\) NP and the density matrix renormalization group annealing conjecture
Parameterized complexity results for a model of theory of mind based on dynamic epistemic logic
Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
Subject-oriented spatial logic
On certifying the UNSAT result of dynamic symmetry-handling-based SAT solvers
Further improvements for SAT in terms of formula length
Characterization and recognition of generalized clique-Helly graphs
Comparative Analysis of Random Generators
Relative complexity of checking and evaluating
Approximate set union via approximate randomization
Approximate set union via approximate randomization
Recent results in hardness of approximation
A hierarchy of tractable satisfiability problems
A multistage view on 2-satisfiability
On the Hamming distance of constraint satisfaction problems.
Unification algorithms cannot be combined in polynomial time.
Symbolic model checking of timed guarded commands using difference decision diagrams
Constraint and satisfiability reasoning for graph coloring
IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?
Computational properties of partial non-deterministic matrices and their logics
Extended resolution simulates binary decision diagrams
Incremental delay enumeration: space and time
Reductions on NP and p-selective sets
Randomness in interactive proofs
Complexity-class-encoding sets
Efficient Algorithms for (3,1) Graphs
Boolean satisfiability in quantum compilation
Automatic scheduling of periodic event networks by SAT solving
Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
On polynomial-time Turing and many-one completeness in PSPACE
Editorial: Symbolic computation and satisfiability checking
A SAT-based preimage analysis of reduced \textsc{Keccak} hash functions
Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities
Context-sensitive fusion grammars and fusion grammars with forbidden context are universal
Mining circuit lower bound proofs for meta-algorithms
Formally verifying the solution to the Boolean Pythagorean triples problem
SPLITTING NUMBER is NP-complete
NP-completeness properties about linear extensions
Complexity of the satisfiability problem for multilinear forms over a finite field
Variability-based model transformation: formal foundation and application
The relative complexity of analytic tableaux and SL-resolution
A switching algorithm for the solution of quadratic Boolean equations
On the complexity of regular resolution and the Davis-Putnam procedure
Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games
scientific article; zbMATH DE number 7092345 (Why is no real title available?)
Dynamical Systems Theory and Algorithms for NP-hard Problems
scientific article; zbMATH DE number 1154176 (Why is no real title available?)
An NP-complete matching problem
Local and global deadlock-detection in component-based systems are NP-hard
Combinatorial PCPs with short proofs
Backdoors to q-Horn
Linearly-growing reductions of Karp's 21 NP-complete problems
Current trends in substructural logics
Perfect state distinguishability and computational speedups with postselected closed timelike curves
Roof duality, complementation and persistency in quadratic 0–1 optimization
Computational experience with an interior point algorithm on the satisfiability problem
Deciding Parity Games in Quasi-polynomial Time
Strongly stable and maximum weakly stable noncrossing matchings
List scheduling algorithms to minimize the makespan on identical parallel machines
Constrained synchronization and subset synchronization problems for weakly acyclic automata
Generating clause sequences of a CNF formula
Generating hard satisfiability problems
An initial study of budgeted Steiner networks
Computing quantum discord is NP-complete
The Deduction Theorem for Strong Propositional Proof Systems
Decidability of NP-complete problems
A primal-dual approximation algorithm for \textsc{minsat}
Independent transversals of hypergraph edges and bipartite bigraphs
Satgraphs and independent domination. I
MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
Nagging: A scalable fault-tolerant paradigm for distributed search
Testing membership: Beyond permutation groups
scientific article; zbMATH DE number 3473353 (Why is no real title available?)
On polynomial time isomorphisms of some new complete sets
Real-time computations with restricted nondeterminism
On the complexity of role colouring planar graphs, trees and cographs
Complexity of dimension three and some related edge-covering characteristics of graphs
Simultaneous visibility representations of undirected pairs of graphs
Statistical mechanics methods and phase transitions in optimization problems
On computing probabilistic abductive explanations
DPLL: the core of modern satisfiability solvers
Strongly stable and maximum weakly stable noncrossing matchings
Improved integral attack on generalized Feistel cipher
Non-standard approaches to integer programming
The complexity of computing the permanent
Towards logical foundations for probabilistic computation
Zero knowledge and circuit minimization
On generic NP-completeness of the Boolean satisfiability problem
Physical portrayal of computational complexity
Towards NP-P via proof complexity and search
Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
Boolean functions with a simple certificate for CNF complexity
P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
Complexity in mechanized hypothesis formation

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)