Having trouble understanding a proof of Mahaney’s theorem

Question

I am reading a blog post of Lance Fortnow, which includes a proof of Mahaney's theorem.

I am not sure why $a’$ cannot be in between $w_i$ and $w_j$ in Case 1, and also why $a’$ cannot be in between $w_0$ and $w_1$ in Case 2.

Can anyone give me some explanation?

Answer 1

Let me recap the proof. We are given a sparse NP-hard language $A$: for each length $n$, there are at most $n^c$ strings of length $n$ in $A$.

For a satisfiable CNF $\varphi$, let $a(\varphi)$ be the lexicographically first satisfying assignment for $\varphi$. We consider the NP language $B$, which consists of all pairs $(\varphi,w)$ such that $\varphi$ is satisfiable and $a(\varphi) \leq w$ (in lexicographic order).

Since $B$ is in NP, there is a polytime reduction $f$ such that $(\varphi,w) \in B$ iff $f(\varphi,w) \in A$. Since $f$ runs in polytime, $|f(\varphi,w)|$ is polynomially bounded, say $|f(\varphi,w)| \leq N$ (where $N$ depends on $n = |(\varphi,w)|$). Since $A$ is sparse, we can bound $$ |\{f(\varphi,w) : w \text{ is an assignment for $\varphi$}\} \cap A| \leq \sum_{k \leq N} k^c =: m, $$ where $m$ is also polynomial in $n$.

We will show how to use $f$ to decide SAT in polynomial time. Given a CNF $\varphi$, we will assume that $\varphi$ is satisfiable, and will attempt to verify it. That is, under the assumption that $\varphi$ is satisfiable, we will run an algorithm that is guaranteed to find a satisfying assignment for $\varphi$. If it succeeds, we can conclude that $\varphi$ is indeed satisfiable (since we have found a satisfying assignment). If it fails, then $\varphi$ couldn't have been satisfiable.

We will use $f$ to determine $a(\varphi)$ using some sort of binary search. The idea is to pick $m+1$ many assignments $w_1,\ldots,w_{m+1}$, equally spaced in assignment space, and to calculate $f(\varphi,w_1), \ldots, f(\varphi,w_{m+1})$. We now consider two cases:

• $f(\varphi,w_i) = f(\varphi,w_j)$ for some $i < j$. If $f(\varphi,w_i) \notin A$ then this means that $a(\varphi) > w_i,w_j$. If $f(\varphi,w_i) \in A$ then this means that $a(\varphi) \leq w_i,w_j$. In both cases, it is clear that $a(\varphi) \notin \{w_i+1,\ldots,w_j\}$ (where $w_i+1$ is the successor assignment in lexicographic order).
• All $f(\varphi,w_i)$ are distinct. By construction, at least one of them is outside of $A$, say $f(\varphi,w_i)$. Then $a(\varphi) > w_i \geq w_1$. In particular, $a(\varphi) \notin \{0,\ldots,w_1\}$, where $0$ is the first assignment in lexicographic order.

Since we chose the $w_i$ to be evenly spaced, in both cases we eliminate a (roughly) $1/m$ fraction of the search space. After $O(nm)$ such iterations, we will be left with only $\operatorname{poly}(n)$ potential values of $a(\varphi)$, and can check them one by one (in order), thereby finding $a(\varphi)$ (if it is there to be found). (I am sketching this part since your question is about the preceding part.)