CNF satisfiability in a subspace and related problems
type: Item
instance of: scholarly article
title: CNF satisfiability in a subspace and related problems
author: Vikraman Arvind
author: Venkatesan Guruswami
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/2108.05914
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7608291
zbMATH Keywords: satisfiability problem
zbMATH Keywords: CNF formulas
zbMATH Keywords: linear equations
zbMATH Keywords: fast exponential algorithms
MaRDI profile type: Publication
OpenAlex ID: W4220759393
cites work: Q5091175
cites work: CSPs with global modular constraints: algorithms and hardness via polynomial representations
cites work: Bridging between 0/1 and linear programming via random walks
cites work: Deterministic APSP, Orthogonal Vectors, and More
cites work: Satisfiability on mixed instances
cites work: Q4393480
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: Parametrized complexity theory.
cites work: Q5743451
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Strong partial clones and the time complexity of SAT problems
cites work: Fine-Grained Time Complexity of Constraint Satisfaction Problems
cites work: Beating Brute Force for Systems of Polynomial Equations over Finite Fields
cites work: Solving satisfiability in less than \(2^ n\) steps
cites work: Q5417690
cites work: The complexity of satisfiability problems
cites work: An algorithm for the satisfiability problem of formulas in conjunctive normal form
cites work: Tinted, detached, and lazy CNF-XOR solving and its applications to counting and sampling
cites work: NP is as easy as detecting unique solutions
DOI: 10.1007/S00453-022-00958-4
description: scientific article; zbMATH DE number 7608291