Journal article:

    Samuel R. Buss,
    "Relating the Bounded Arithmetic and Polynomial-Time Hierarchies."
    Annals of Pure and Applied Logic
, 75 (1995) 67-77.

    Download journal article version: postscript or PDF.

    Abstract: The bounded arithmetic theory $S_2$ is finitely axiomatized if and only if the polynomial hierarchy provably collapses. If $T^i_2$ equals~$S^{i+1}_2$ then $T^i_2$ is equal to $S_2$ and proves that the polynomial time hierarchy collapses to $\Sigma^p_{i+3}$, and, in fact, to the Boolean hierarchy over~$\Sigma^p_{i+2}$ and to $\Sigma^p_{i+1}/poly$.

Back to Sam Buss's publications page.