We develop a method for establishing the independence of some ∑ i b ( α ) formulas from S 2 i ( α ) . In particular, we show that T 2 i ( α ) is not ∀ ∑ 2 i ( α ) -conservative over S 2 i ( α ) . We characterize the ∑ i b -definable functions of T 2 1 as being precisely the functions definable as projections of polynomial local search (PLS) problems.
No takes yet. Share an insight, caveat, or question.
Buss et al. (1994) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: