Next: MAXIMUM RENAMABLE HORN SUBFORMULA
Up: Miscellaneous
Previous: Miscellaneous
  Index
- INSTANCE:
Set M of truth assignments on n variables.
- SOLUTION:
A Horn core of M, i.e., a subset
such that M' is equal to
the set of truth assignments satisfying a Horn boolean formula.
- MEASURE:
The cardinality of the core, i.e., .
- Bad News:
Not in APX [299].
Viggo Kann
2000-03-20