# Complexity of ODD-SMALLER-SAT

While familiarizing myself with polynomial hierarchy, I used this book which is written by Ingo Wegener. Now I'm practicing, and on page 132 I met this exercise:

Let us consider a Boolean formula $$\phi$$ on the variables $$x_1, ...,x_n$$. Each $$n$$ bit vector $$\overline x \in \{0,1\}^n$$ is a possible assignment to variables and these vectors can be naturally classified in alphabetical order. The ODD-SMALLER-SAT-DECISION problem is to determine, being given $$\phi$$, if the smallest assignment $$x$$ which is satisfactory is such that $$x_n = 1$$.

How to prove that this problem is part of the complexity class $$\Delta_2$$?

## 1 Answer

Given $$\phi$$ and an assignment $$\overline{y}$$, the problem of deciding if there exists a satisfying assignment $$\overline{x} \le \overline{y}$$ (w.r.t. the lexicographical order) is in NP. This can be seen by either designing a nondeterministic Turing machine that solves the problem in polynomial time (nondeterministically guess $$\overline{x}$$, then deterministically check if $$\overline{x} \le \overline{y}$$ and $$\phi(\overline{x}) = \top$$, if so accept, otherwise reject), or by noticing that $$\overline{x}$$ itself is a yes-certificate for the instance (that can be deterministically checked in polynomial-time).

Then your original problem is in $$\Delta_2 = P^{NP}$$: perform a binary search on the space of the $$2^n$$ possible assignments to find the smallest satisfying assignment $$\overline{x}^*$$ for $$\phi$$. This can be done by repeatedly solving the above problem, each time halving the search space. After $$O(\log 2^n) = O(n)$$ iterations you are left with $$\overline{x}^*$$. Check whether $$\overline{x}^*_n = 1$$ and answer accordingly.

• Thank you for your help. Now it's clear to me. – tala Apr 3 '20 at 17:41