Satisfiability with index dependency

DOI10.1007/s11390-012-1253-9zbMath1280.68110MaRDI QIDQ2637283

Hongyu Liang, Jing (Selena) He

Publication date: 11 February 2014

Published in: Journal of Computer Science and Technology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11390-012-1253-9

zbMATH Keywords

dichotomy; Boolean satisfiability problem; index-dependency; index-width

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)