Now showing items 1-10 of 10

• #### The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection ﻿

(Cornell University, 1989-05)
We show that if the Boolean hierarchy collapses to its $k^{th}$ level, then the polynomial hierarchy collapses to the $k^{th}$ level of the difference hierarchy of $\Sigma^{P}_{2}$ languages.
• #### An Example of a Theorem that has Contradictory Relativizations and a Diagonalization Proof ﻿

(Cornell University, 1989-11)
We construct a computable space bound $S(n)$, with $n^{2} less than S(n) less than n^{3}$ and show by diagonalization that DSPACE [$S(n)$] = DSPACE [$S(n)$ log $n$]. Moreover, we can show that there exists an oracle $A$ ...
• #### On Computing Boolean Connectives of Characteristic Functions ﻿

(Cornell University, 1990-05)
• #### Structural Complexity Theory: Recent Surprises ﻿

(Cornell University, 1990-04)
This paper reviews the impact of some recent results on the research paradigms in structural complexity theory.