scientific article; zbMATH DE number 1113996

MaRDI QIDQ4375761zbMATH OpenFDO

Authors Oliver Kullmann

Publication date 14 June 1998

zbMATH Keywords

3-SAT decisionexponential lower boundSAT-algorithmsworst-case analysis

Mathematics Subject Classification ID

Classical propositional logic (03B05) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• New methods for 3-SAT decision and worst-case analysis
• The worst-case upper bound for exact 3-satisfiability with the number of clauses as the parameter
• New worst-case upper bounds for SAT
• New worst-case upper bounds for SAT
• scientific article; zbMATH DE number 6469161
• Improved bound for the PPSZ/Schöning-algorithm for 3-SAT
• Improved randomized algorithms for 3-SAT
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• A new upper bound for 3-SAT

Cited in

(11)

• Investigations on autark assignments
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• New methods for 3-SAT decision and worst-case analysis
• On a generalization of extended resolution
• Separating signs in the propositional satisfiability problem
• Efficient 3-SAT algorithms in the tile assembly model
• Improving efficiency of 3-SAT-solving tile systems
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• DRAT and propagation redundancy proofs without new variables
• Local search algorithms for SAT: Worst-case analysis
• Lower bounds for set-blocked clauses proofs

This page was built for publication:

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