99-26: A Short Note on Linear Autarkies, q-Horn Formulas and the Complexity Index

DIMACS TR: 99-26

A Short Note on Linear Autarkies, q-Horn Formulas and the Complexity Index

Author: Hans van Maaren

ABSTRACT
It is shown that the tractable class of CNF formulas solvable by Linear Autarkies properly contains the class of q-Horn formulas and that it is incomparable with SLUR.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-26.ps.gz

DIMACS Home Page