The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
type: Item
instance of: scholarly article
title: The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
zbMATH Open document ID: 1495.68158
DOI: 10.1145/3492336
author: Victor Lagerkvist
author: Magnus Wahlström
published in: ACM Transactions on Computation Theory
publication date: 2022-09-24T00:00:00Z
Mathematics Subject Classification ID: 68R07
Mathematics Subject Classification ID: 08A70
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7592189
zbMATH Keywords: fine-grained complexity
zbMATH Keywords: satisfiability problems
zbMATH Keywords: constraint satisfaction problems
zbMATH Keywords: universal algebra
MaRDI profile type: MaRDI publication profile
full work available at URL: https://doi.org/10.1145/3492336
OpenAlex ID: W4200344539
Wikidata QID: Q130949699
Recommended article: Structural tractability of enumerating CSP solutions
Recommended article: The Structure of Tractable Constraint Satisfaction Problems
Recommended article: Fine-Grained Time Complexity of Constraint Satisfaction Problems
Recommended article: Complexity and Algorithms for Well-Structured k-SAT Instances
Recommended article: The complexity of constraint satisfaction revisited
Recommended article: STACS 2004
Recommended article: On Problems as Hard as CNF-SAT
Recommended article: On the relations between SAT and CSP enumerative algorithms
Recommended article: A unified theory of structural tractability for constraint satisfaction problems
description: scientific article; zbMATH DE number 7592189