Complexity of ODD-SMALLER-SAT

Question

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$?

Answer 1

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.