<p>OptP-complete. <a href="http://www.sciencedirect.com/science/article/pii/0022000088900396">Krentel</a> showed that MAX-SAT, finding the lexicographically maximum satisfying assignment, is OptP-complete and the reduction above reduces Max-SAT to ILP. ILP sits in OptP pretty much by definition.</p>

<p>Note that you need n calls to an NP-oracle to solve ILP via binary search, O(log n) isn't sufficient. </p>

<p>There really isn't much of a connection to UP, though Mulmuley, Vazirani and Vazirani <a href="http://dx.doi.org/10.1145/28395.383347">give an isolation lemma</a> that gives an alternate proof of Valiant-Vazirani via a maximization problem.</p>

CC BY-SA 3.0
2014-07-17T13:42:08.680Z
2014-07-17T13:42:08.680Z
Lance Fortnow
<p>Probably this is well known. There is probabilistic reduction
from SAT to Unique SAT (0 or 1 solutions).</p>

<p>According to <a href="https://cstheory.stackexchange.com/questions/25154/would-derandomizing-the-reduction-from-sat-to-unique-sat-imply-np-and-conp-a">answer and comments</a> derandomizing the reduction would imply $PH \subseteq \oplus P$.</p>

<p>There is simple reduction from SAT to 0,1 integer linear program with
zero or one solutions.</p>

<p>Given SAT formula $\phi$ on variables $x_1,\ldots x_n$,
introduce binary variables $b_i \in \{0,1\}$.</p>

<p>Define map literals to linear polynomials $f(x_i)=b_i$ and
$f(\lnot x_i)=1-b_i$.</p>

<p>For a clause $l_1 \lor \cdots \lor l_k$ add
constraint $\sum_{i=1}^k f(l_i) \ge 1$.</p>

<p>So far the solutions of the constraints are in one
to one correspondence with the solutions of $\phi$.</p>

<p>To make the solution unique, add the optimization</p>

<p>$$\text{maximize} \sum_{i=1}^n 2^{(i-1)}b_i$$</p>

<p>Two sets of distinct powers of two have equal sums
iff the sets are equal, so the objective function
have unique maximum if the constraints are satisfied.
The ordering of $x_i$ doesn't matter.
So the 0,1 ILP has zero or one solutions and it is
not easier than NP-complete and coNP-complete.</p>

<blockquote>
  <p>In what complexity class is solving the 0,1 ILP?</p>
</blockquote>

<p>As far as I know ILP are not a complexity class.</p>

<p>$\log_2(n)$ calls to NP oracle would solve it via
binary search, though I don't see a direct reduction to
SAT.</p>

<p>This appears close to UP though there is no certificate.</p>

<cc.complexity-theory><sat><integer-programming><unique-solution>
Reduction from SAT to 0,1 integer linear program with zero or one solutions
joro
# Reduction from SAT to 0,1 integer linear program with zero or one solutions

(Asked by: username_0 on 2014-07-17)

Probably this is well known. There is probabilistic reduction
from SAT to Unique SAT (0 or 1 solutions).

According to [answer and comments](https://cstheory.stackexchange.com/questions/25154/would-derandomizing-the-reduction-from-sat-to-unique-sat-imply-np-and-conp-a) derandomizing the reduction would imply $PH \subseteq \oplus P$.

There is simple reduction from SAT to 0,1 integer linear program with
zero or one solutions.

Given SAT formula $\phi$ on variables $x\_1,\ldots x\_n$,
introduce binary variables $b\_i \in \{0,1\}$.

Define map literals to linear polynomials $f(x\_i)=b\_i$ and
$f(\lnot x\_i)=1-b\_i$.

For a clause $l\_1 \lor \cdots \lor l\_k$ add
constraint $\sum\_{i=1}^k f(l\_i) \ge 1$.

So far the solutions of the constraints are in one
to one correspondence with the solutions of $\phi$.

To make the solution unique, add the optimization

$$\text{maximize} \sum\_{i=1}^n 2^{(i-1)}b\_i$$

Two sets of distinct powers of two have equal sums
iff the sets are equal, so the objective function
have unique maximum if the constraints are satisfied.
The ordering of $x\_i$ doesn't matter.
So the 0,1 ILP has zero or one solutions and it is
not easier than NP-complete and coNP-complete.

> In what complexity class is solving the 0,1 ILP?

As far as I know ILP are not a complexity class.

$\log\_2(n)$ calls to NP oracle would solve it via
binary search, though I don't see a direct reduction to
SAT.

This appears close to UP though there is no certificate.

**Tags:** cc.complexity-theory, sat, integer-programming, unique-solution


---

## 1 answers

### Answer by username_1 on 2014-07-17. Score: 11 | Accepted answer

OptP-complete. [Krentel](http://www.sciencedirect.com/science/article/pii/0022000088900396) showed that MAX-SAT, finding the lexicographically maximum satisfying assignment, is OptP-complete and the reduction above reduces Max-SAT to ILP. ILP sits in OptP pretty much by definition.

Note that you need n calls to an NP-oracle to solve ILP via binary search, O(log n) isn't sufficient.

There really isn't much of a connection to UP, though Mulmuley, Vazirani and Vazirani [give an isolation lemma](http://dx.doi.org/10.1145/28395.383347) that gives an alternate proof of Valiant-Vazirani via a maximization problem.


---

