Approximating Succinct MaxSat.
We study the approximability of the version of MAXSAT where exponentially large instances are succinctly represented using circuits. First, we prove that the NP-hardness for approximating MAXSAT can be lifted to a corresponding NEXP-hardness for approximating circuit-succinct MAXSAT for some constan...
| Hauptverfasser: | , |
|---|---|
| Format: | Journal article |
| Sprache: | English |
| Veröffentlicht: |
2005
|