Generating hard satisfiability problems
From MaRDI portal
Recommendations
Cites work
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- A threshold for unsatisfiability
- Branch-and-cut solution of inference problems in propositional logic
- Critical behavior in the computational cost of satisfiability testing
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Easy problems are sometimes hard
- scientific article; zbMATH DE number 437557 (Why is no real title available?)
- scientific article; zbMATH DE number 3904630 (Why is no real title available?)
- scientific article; zbMATH DE number 30299 (Why is no real title available?)
- scientific article; zbMATH DE number 67483 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256700 (Why is no real title available?)
- scientific article; zbMATH DE number 1995157 (Why is no real title available?)
- scientific article; zbMATH DE number 956863 (Why is no real title available?)
- Many hard examples for resolution
- On the complexity of regular resolution and the Davis-Putnam procedure
- Outlier..........s
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Resolution vs. cutting plane solution of inference problems: Some computational experience
- Solving the satisfiability problem by using randomized approach
- Some pitfalls for experimenters with random SAT
- The complexity of theorem-proving procedures
- The intractability of resolution
Cited in
(70)- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes
- Remote Agent: to boldly go where no AI system has gone before
- A two-phase algorithm for solving a class of hard satisfiability problems
- Easy problems are sometimes hard
- Generalized satisfiability problems: Minimal elements and phase transitions.
- How to fake an RSA signature by encoding modular root finding as a SAT problem
- Experimental complexity analysis of continuous constraint satisfaction problems.
- Backtracking algorithms for disjunctions of temporal constraints
- Nagging: A scalable fault-tolerant paradigm for distributed search
- Measuring instance difficulty for combinatorial optimization problems
- On SAT instance classes and a method for reliable performance experiments with SAT solvers
- Partitioning methods for satisfiability testing on large formulas
- A sharp threshold in proof complexity yields lower bounds for satisfiability search
- An improved algorithm for the (n, 3)-MaxSAT problem: asking branchings to satisfy the clauses
- On the hierarchical community structure of practical Boolean formulas
- New models for generating hard random Boolean formulas and disjunctive logic programs
- A computational complexity analysis of tunable type inference for Generic Universe Types
- Large hypertree width for sparse random hypergraphs
- Implementing semantic merging operators using binary decision diagrams
- Partition-based logical reasoning for first-order and propositional theories
- Compiling problem specifications into SAT
- A new constraint test-case generator and the importance of hybrid optimizers
- Generating instances for MAX2SAT with optimal solutions
- On the complexity of unfrozen problems
- Phase transitions of PP-complete satisfiability problems
- Experimental results on the crossover point in random 3-SAT
- Some pitfalls for experimenters with random SAT
- A machine learning system to improve the performance of ASP solving based on encoding selection
- Balance and filtering in structured satisfiable problems. (Preliminary report)
- Generating Diverse Solutions in SAT
- On the Complexity of Estimating the Size of a Test Set
- Hard satisfiable clause sets for benchmarking equivalence reasoning techniques
- Locality and hard SAT-instances
- GoRRiLA and Hard Reality
- Hierarchical Hardness Models for SAT
- scientific article; zbMATH DE number 5726469 (Why is no real title available?)
- Generating hard satisfiable formulas by hiding solutions deceptively
- scientific article; zbMATH DE number 15884 (Why is no real title available?)
- scientific article; zbMATH DE number 169728 (Why is no real title available?)
- scientific article; zbMATH DE number 1113991 (Why is no real title available?)
- On generating all solutions of generalized satisfiability problems
- scientific article; zbMATH DE number 1954175 (Why is no real title available?)
- Complexity of coloring random graphs: an experimental study of the hardest region
- Fractional edge cover number of Model RB
- scientific article; zbMATH DE number 2165692 (Why is no real title available?)
- scientific article; zbMATH DE number 7453125 (Why is no real title available?)
- Satisfiability in Boolean logic (SAT problem) is polynomial
- Theory and Applications of Satisfiability Testing
- Sgen1, a generator of small but difficult satisfiability benchmarks
- Algorithms for Effective Argumentation in Classical Propositional Logic: A Connection Graph Approach
- scientific article; zbMATH DE number 2196508 (Why is no real title available?)
- Theory and Applications of Satisfiability Testing
- scientific article; zbMATH DE number 2243408 (Why is no real title available?)
- On super strong ETH
- Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Satisfiability threshold for power law random 2-SAT in configuration model
- A wealth of SAT distributions with planted assignments
- A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
- Rigorous results for random (2+p)-SAT
- Results related to threshold phenomena research in satisfiability: Lower bounds
- Generating Difficult CNF Instances in Unexplored Constrainedness Regions
- How to split a logic program
- Faster random k-CNF satisfiability
- Smoothed analysis of deterministic discounted and Mean-payoff games
- Parameterized inapproximability of Morse matching
- Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
- An improved generator for 3-CNF formulas
- A competitive and cooperative approach to propositional satisfiability
This page was built for publication: Generating hard satisfiability problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2674174)
