Section 7.2.2.2: Satisfiability

Exercise 169. ▶ [HM30] (T. Ahmed, O. Kullmann.) Excellent results have been obtained in some problems when the branch variable in step L3 is chosen to minimize the quantity $\tau(H(l), H(\bar{l}))$, where $\tau(a, b)$ is the positive solution to $\tau^{-a} + \tau^{-b} = 1$. (For example, $\tau(1, 2) = \phi \approx 1.62$ and $\tau(\sqrt{2}, \sqrt{2}) = 2^{1/\sqrt{2}} \approx 1.63$, so we prefer $(1, 2)$ to $(\sqrt{2}, \sqrt{2})$.) Given a list of pairs of positive numbers $(a_1, b_1), \ldots, (a_n, b_n)$, what's an efficient way to determine an index $j$ that minimizes $\tau(a_j, b_j)$, without computing logarithms?

Verified: no
Solve time: 2m57s

---

The essential observation is that one does not need to compute the value of

$$ \tau(a,b) $$

itself in order to compare two candidates.

Let

$$ \tau(a,b)>1 $$

be the unique solution of

$$ \tau^{-a}+\tau^{-b}=1. $$

For two pairs $(a,b)$ and $(c,d)$, we seek to determine whether

$$ \tau(a,b)<\tau(c,d) $$

without solving either defining equation.

Define

$$ F_{a,b}(t)=t^{-a}+t^{-b},\qquad t>1. $$

Since

$$ F'_{a,b}(t)

-a t^{-a-1}-b t^{-b-1}<0, $$

the function is strictly decreasing, and

$$ F_{a,b}(\tau(a,b))=1. $$

Hence, for every $t>1$,

$$ F_{a,b}(t) \begin{cases}

1,&t<\tau(a,b),\ =1,&t=\tau(a,b),\ <1,&t>\tau(a,b). \end{cases} $$

Now suppose we wish to compare

$$ \tau_1=\tau(a,b),\qquad \tau_2=\tau(c,d). $$

Instead of computing either value, perform a simultaneous bisection.

Choose any initial interval containing both roots. For example,

$$ L=1. $$

Since

$$ \lim_{t\to\infty}F_{a,b}(t)=0 $$

for every pair, repeatedly double an upper bound

$$ U=2,4,8,\ldots $$

until

$$ F_{a,b}(U)<1 \quad\text{and}\quad F_{c,d}(U)<1. $$

Then both roots lie in

$$ (L,U). $$

At each step let

$$ M=\frac{L+U}{2}. $$

Evaluate only

$$ F_{a,b}(M),\qquad F_{c,d}(M). $$

There are three possibilities.

1. If both values exceed $1$, then

$$ M<\tau_1,\qquad M<\tau_2, $$

so both roots lie in $(M,U)$. Replace $L$ by $M$. 2. If both values are below $1$, then

$$ \tau_1<M,\qquad \tau_2<M, $$

so both roots lie in $(L,M)$. Replace $U$ by $M$. 3. If one value exceeds $1$ and the other is below $1$, then the midpoint separates the two roots. For example,

$$ F_{a,b}(M)>1,\qquad F_{c,d}(M)<1 $$

implies

$$ \tau_1>M>\tau_2, $$

hence

$$ \tau_2<\tau_1. $$

The comparison is finished.

Thus every bisection step either shrinks the common interval containing both roots or immediately determines their order. No logarithms are required. The only numerical operations are exponentiations with the common base $M$.

To find the minimum among

$$ (a_1,b_1),\ldots,(a_n,b_n), $$

maintain the current best candidate. Compare each remaining pair with the current best using the comparison procedure above. If

$$ \tau(a_i,b_i)<\tau(a_{\text{best}},b_{\text{best}}), $$

replace the current best by $i$; otherwise keep the current best. After $n-1$ comparisons, the remaining index minimizes $\tau$. If a comparison ends with equality, either index may be retained, since the problem asks for a minimizing index, not necessarily a unique one.

This method performs exactly $n-1$ comparisons, never computes any logarithms, and never solves the defining equation for an individual pair. Each comparison uses only evaluations of

$$ t^{-a}+t^{-b} $$

at common trial values until the two roots are separated. This is the efficient comparison procedure requested in the exercise.