Now showing items 1-8 of 8

    • 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.
    • Deterministic Polynomial Time O(log n) Queries 

      Kadin, Jim (Cornell University, 1986-08)
      $P^{NP[\log n]}$ is the class of languages recognizable by determining polynomial time machines that make $O(\log n)$ queries to an oracle for NP. Many of the languages related to optimal solution sizes of NP optimization ...
    • Is One NP Question as Powerful as Two? 

      Kadin, Jim (Cornell University, 1987-06)
      For any integer $k$, $P^{SAT[k]}$ is the class of languages accepted by deterministic polynomial time oracle machines that make at most $k$ queries to an oracle for SAT. It is easy to see that $P^{SAT[1]} \subseteq D^{P} ...
    • A Note on the Complexity of Goedel Numberings and Isomorphisms 

      Kadin, Jim (Cornell University, 1981-08)
      Some problems involved in looking at recursive function theory and thinking about the complexity of computations are discussed. Complexity classes of Goedel numberings are studied where a Goedel numbering is in a given ...
    • 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 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 ...
    • The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses 

      Kadin, Jim (Cornell University, 1987-06)
      The structure of the Boolean hierarchy (BH) is related to the polynomial time hierarchy (PH) by showing that if the BH collapses, then $PH \subseteq \Delta^{P}_{3}$.
    • Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy 

      Kadin, Jim (Cornell University, 1988-03)
      The polynomialtime many-one and Turing reducibilities, Karp and Cook reducibilities respectively, play an major role in computational complexity theory, particularly in the study of such classes as P, NP, the polynomial ...