An improved upper bound for SAT

DOI10.1016/J.TCS.2021.06.045OpenAlexW3179743149MaRDI QIDQ820534FDOQ820534

Authors: Huairui Chu, Mingyu Xiao, Zhe Zhang 

Publication date: 27 September 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2007.03829

Recommendations

• Algorithms and Computation
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 1522934
• New worst-case upper bounds for SAT
• New Upper Bounds for Maximum Satisfiability

zbMATH Keywords

exact algorithmsSATparameterized algorithmsamortized analysis

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Exact exponential algorithms.
• The complexity of theorem-proving procedures
• On the complexity of \(k\)-SAT
• A Machine-Oriented Logic Based on the Resolution Principle
• A Computing Procedure for Quantification Theory
• Solving satisfiability in less than \(2^ n\) steps
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• STACS 2004
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Theory and Applications of Satisfiability Testing
• An efficient fixed-parameter algorithm for 3-hitting set
• New worst-case upper bounds for SAT
• Algorithms and Computation
• A satisfiability tester for non-clausal propositional calculus
• Two systems for proving tautologies, based on the split method
• An Improved SAT Algorithm in Terms of Formula Length
• Title not available (Why is that?)
• Title not available (Why is that?)
• Faster \(k\)-SAT algorithms using biased-PPSZ
• Theory and Applications of Satisfiability Testing

Cited In (7)

• Algorithms and Computation
• Title not available (Why is that?)
• On the possibility of faster \textsc{SAT} algorithms
• Theory and Applications of Satisfiability Testing
• SAT-Based Horn Least Upper Bounds
• About some UP-based polynomial fragments of SAT
• Further improvements for SAT in terms of formula length

This page was built for publication: An improved upper bound for SAT

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