Range Avoidance, Arthur-Merlin, and TFNP

Range avoidance (Avoid) is the computational problem in which the input is an expanding circuit C : 0, 1 n → 0, 1 n+1 and the goal is to find a string y ∈ 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.