Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem

We give a new characterization of the strict. for all Sigma(b)(j) sentences provable using Sigma(b)(k) induction, for 1 <= j <= k. As a small application we show that, in a certain sense, Buss's witnessing theorem for strict Sigma(k)(b) formulas already holds over the relatively weak theory PV. We exhibit a combinatorial principle with the property that a lower bound for it in constant- depth Frege would imply that the narrow CNFs with short depth j Frege refutations form a strict hierarchy with j, and hence that the relativized bounded arithmetic hierarchy can be separated by a family of for all Sigma(b)(1) sentences.