Journal article:

    Samuel R. Buss and Jan Krajicek.
    "An application of Boolean complexity to separation problems in bounded arithmetic."
    Proceedings of the London Mathematical Society 69 (1994) 1-21.

Download conference article: postscript or PDF

    Abstract: We develop a method for establishing the independence of some $\Sigma^b_i(\alpha)$-formulas from $S^i_2(\alpha)$. In particular, we show that $T^i_2(\alpha)$ is not $\forall\Sigma^b_i(\alpha)$-conservative over $S^i_2(\alpha)$.
    We characterize the $\Sigma^b_1$-definable functions of~$T^1_2$ as being precisely the functions definable as projections of polynomial local search (PLS) problems.

Back to Sam Buss's publications page.