Range avoidance (Avoid) is the computational problem in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$ and the goal is to find a string $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. Avoid was introduced recently by Kleinberg, Korten, Mitropolsky, and Papadimitriou [ITCS 2021] as an example of a total search problem that appears not to live in TFNP but does live in the second level of the total function polynomial hierarchy. Since then, Avoid has found surprising applications throughout complexity theory, and in theoretical computer science more broadly.
Our main results are as follows.
1) We show that any decision problem that efficiently reduces to Avoid is in AM $\cap$ coAM (even for promise problems, and even if the reduction is randomized and makes many adaptive queries). This in particular shows that NP-hardness of Avoid would collapse the polynomial hierarchy, answering an open question that has arisen numerous times in the literature.
2) We show an efficient randomized reduction from Avoid to a problem in TFNP that succeeds with probability $1-\varepsilon$ for any $\varepsilon \geq 1/\mathrm{poly}(n)$ (under complexity-theoretic assumptions). This provides additional evidence that Avoid is unlikely to be NP-hard. And, it shows that, though Avoid itself is almost certainly not in TFNP, it is in some sense extremely close to lying in TFNP. The randomness in our reduction seems necessary, since Chen and Li [STOC 2024] showed (under cryptographic assumptions) that Avoid $\notin$ SearchNP, while a deterministic reduction from Avoid to a TFNP problem would place Avoid in SearchNP.
The high-level idea behind these two results is a rather simple ``search Arthur-Merlin-Arthur protocol for Avoid.'' And, a key technical tool that we use in all of our results is a novel AM protocol for upper bounding the size of the image of a circuit. This latter protocol can be viewed as a sort of dual of the celebrated set-size lower bound protocol due to Goldwasser and Sipser [STOC 1986]. Both protocols seem likely to be of independent interest.
