Complexity Results for Linear XSAT-Problems

DOI10.1007/978-3-642-14186-7_21zbMath1306.68046OpenAlexW1519201794MaRDI QIDQ4930593

Ewald Speckenmeyer, Tatjana Schmidt, Stefan Porschen

Publication date: 29 September 2010

Published in: Theory and Applications of Satisfiability Testing – SAT 2010 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14186-7_21

zbMATH Keywords

regularityNP-completenessfinite projective planeexact satisfiabilitylinear formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

XSAT and NAE-SAT of linear CNF classes

This page was built for publication: Complexity Results for Linear XSAT-Problems