MAXIMUM HORN CORE

• INSTANCE: Set M of truth assignments on n variables.

• SOLUTION: A Horn core of M, i.e., a subset $M' \subseteq M$ such that M' is equal to the set of truth assignments satisfying a Horn boolean formula.

• MEASURE: The cardinality of the core, i.e., $\vert M'\vert$.

  
  

• Bad News: Not in APX [299].