CNF satisfiability in a subspace and related problems

DOI10.1007/S00453-022-00958-4MaRDI QIDQ2093572zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Venkatesan Guruswami

Publication date 27 October 2022

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

CNF formulasfast exponential algorithmslinear equationssatisfiability problem

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Recommendations

• CNF satisfiability in a subspace and related problems
• An improved exponential-time algorithm for k -SAT
• Why almost all satisfiable k-CNF formulas are easy
• Solving and sampling with many solutions
• Improved algorithms for sparse MAX-SAT and MAX-k-CSP

Cites work

• A satisfiability algorithm for \(\mathrm{AC}^0\)
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• Beating brute force for systems of polynomial equations over finite fields
• Bridging between 0/1 and linear programming via random walks
• CSPs with global modular constraints: algorithms and hardness via polynomial representations
• Deterministic APSP, Orthogonal Vectors, and More
• Fine-grained time complexity of constraint satisfaction problems
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• NP is as easy as detecting unique solutions
• On the complexity of k-SAT
• On the parameterized complexity of multiple-interval graph problems
• On the possibility of faster \textsc{SAT} algorithms
• Parametrized complexity theory.
• Satisfiability on mixed instances
• Solving satisfiability in less than \(2^ n\) steps
• Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction
• Strong partial clones and the time complexity of SAT problems
• The complexity of satisfiability problems
• Tinted, detached, and lazy CNF-XOR solving and its applications to counting and sampling
• Which problems have strongly exponential complexity?

Cited in

(10)

• 2-cnfs and logical embeddings
• On the complexity of equational problems in CNF
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Satisfiability of acyclic and almost acyclic CNF formulas
• Satisfiability of acyclic and almost acyclic CNF formulas
• On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances
• A CNF Formula Hierarchy over the Hypercube
• Testing the satisfiability of algebraic formulas over the field of two elements
• CNF satisfiability in a subspace and related problems
• Some remarks on subclass containment problems for several classes of dpda's

This page was built for publication: CNF satisfiability in a subspace and related problems

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