JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Kadin, Jim"
Now showing items 18 of 8

The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection
Chang, Richard; Kadin, Jim (Cornell University, 198905)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, 198608)$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, 198706)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, 198108)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, 199005)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, 199005)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, 198706)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, 198803)The polynomialtime manyone 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 ...