Now showing items 1-10 of 10

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

      Chang, Richard; Kadin, Jim (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 

      Chang, Richard (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 

      Chang, Richard; Kadin, Jim (Cornell University, 1990-05)
      We study the existence of polynomial time Boolean connective functions for languages. A language $L$ has an AND function if there is a polynomial time $f$ such that $f(x,y) \in L \Longleftrightarrow x \in L$ and $y \in ...
    • On IP=PSPACE and Theorems with Narrow Proofs 

      Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj (Cornell University, 1990-05)
      Very recently, it was shown that the class of languages with interactive proofs, IP, is exactly the class PSPACE. This surprising result elegantly places IP in the standard classification of feasible computations. ...
    • On the Structure of Bounded Queries to Arbitrary NP Sets 

      Chang, Richard (Cornell University, 1988-11)
      In [Kad87b], Kadin showed that if the Polynomial Hierarchy (PH) has infinitely many levels, then for all $k$, $P^{SAT[k]} \subseteq P^{SAT[k+1]}$. In this paper, we extend Kadin's technique to show that a proper query ...
    • On The Structure Of NP Computations Under Boolean Operators 

      Chang, Richard (Cornell University, 1991-11)
      This thesis is mainly concerned with the structural complexity of the Boolean Hierarchy. The Boolean Hierarchy is composed of complexity classes constructed using Boolean operators on NP computations. The thesis begins ...
    • On the Structure of Uniquely Satisfiable Formulas 

      Chang, Richard; Kadin, Jim (Cornell University, 1990-05)
      This paper presents some new results on the computational complexity of the set of uniquely satisfiable Boolean formulas (USAT). Valiant and Vazirani showed that USAT is complete for the class $D^{P}$ under randomized ...
    • Random Reductions in the Boolean Hierarchy are Not Robust. 

      Chang, Richard; Rohatgi, Pankaj (Cornell University, 1990-10)
      We investigate random reductions from complete sets in the Boolean Hierarchy to their complements. We show that under the assumption that the Polynomial Hierarchy is infinite, the error probability of such reductions ...
    • A Relationship between Difference Hierarchies and Relativized Polynomial Hierarchies. 

      Beigel, Richard; Chang, Richard; Ogiwara, Mitsunori (Cornell University, 1991-01)
      Chang and Kadin have shown that if the difference hierarchy over NP collapses to level $k$, then the polynomial hierarchy (PH) is equal to the $k$th level of the difference hierarchy over $\Sigma_{2}^{p}$. We simplify ...
    • Structural Complexity Theory: Recent Surprises 

      Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj (Cornell University, 1990-04)
      This paper reviews the impact of some recent results on the research paradigms in structural complexity theory.