scientific article; zbMATH DE number 1113991
From MaRDI portal
Publication:4375756
zbMath0889.68073MaRDI QIDQ4375756
David G. Mitchell, Stephen A. Cook
Publication date: 2 June 1998
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Complexity of proofs (03F20)
Related Items (37)
Complete on average Boolean satisfiability ⋮ An improved generator for 3-CNF formulas ⋮ Many hard examples in exact phase transitions ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Backdoors to Satisfaction ⋮ The state of SAT ⋮ Backdoor sets for DLL subsolvers ⋮ Survey propagation: An algorithm for satisfiability ⋮ A weight-balanced branching rule for SAT ⋮ On black-box optimization in divide-and-conquer SAT solving ⋮ A SAT-based preimage analysis of reduced \textsc{Keccak} hash functions ⋮ Random Instances of W[2-Complete Problems: Thresholds, Complexity, and Algorithms] ⋮ Further improvements for SAT in terms of formula length ⋮ A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ How to fake an RSA signature by encoding modular root finding as a SAT problem ⋮ Toward a model for backtracking and dynamic programming ⋮ A taxonomy of exact methods for partial Max-SAT ⋮ Circuit lower bounds in bounded arithmetics ⋮ Simple search methods for finding a Nash equilibrium ⋮ Fractional Edge Cover Number of Model RB ⋮ Partition-based logical reasoning for first-order and propositional theories ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ Finding Effective SAT Partitionings Via Black-Box Optimization ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ On SAT instance classes and a method for reliable performance experiments with SAT solvers ⋮ Rigorous results for random (\(2+p)\)-SAT ⋮ Unnamed Item ⋮ Threshold values of random K‐SAT from the cavity method ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ Parallel Logical Cryptanalysis of the Generator A5/1 in BNB-Grid System ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Super Strong ETH ⋮ Locally consistent constraint satisfaction problems ⋮ Large hypertree width for sparse random hypergraphs ⋮ Hard satisfiable 3-SAT instances via autocorrelation ⋮ A fast algorithm for SAT in terms of formula length
Uses Software
This page was built for publication: