Now showing items 1-8 of 8

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

(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? ﻿

(Cornell University, 1987-06)
• #### On the Structure of Uniquely Satisfiable Formulas ﻿

(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 ﻿

(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 ﻿

(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 ...