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


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.

| cite | improve this answer | |
  • $\begingroup$ Thank you for your help. Now it's clear to me. $\endgroup$ – tala Apr 3 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.