Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy

Other Titles



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 time hierarchy (PH), and PSPACE. In this thesis, we consider polynomial time Turing reducibilities with various restricted oracle access mechanisms such as restrictions on the number of queries allowed or requiring that all queries be made at once, in parallel. Such restrictions are related to polynomial time truth-table and bounded truth-table reducibilities. We focus mostly on classes of languages reducible to NP sets via these reducibilities. For any integer k,PNP[k] is the class of languages recognizable in polynomial time with k queries to an oracle from NP. The query hierarchy, QH, is kPNP[k]. The class PNP[logn] is the set of languages recognizable with O(logn) queries. Two related hierarchies are the Boolean hierarchy Boolean hierarchy (BH) and the parallel query hierarchy (QH||). The BH, QH, and QH|| intertwine to form a rich structure within PNP: NP co-NP PNP[1]PNP[2]⊆⋯⊆QH=QH||=BHPNP[logn]PNP. We show that the structure of these classes is closely tied to the existence of nonuniform algorithms for NP and co-NP languages and to the structure of the PH as a whole. We improve Mahaney's result for sparse Turing-complete sets for NP by showing that if there exists a sparse set SNP such that co-NP NPS, then PH PNP[logn]. We show that there are relativized worlds where this collapse is optimal, and thus we provide a clear distinction between the effects of a sparse many-one-complete set and a sparse Turing-complete set for NP. We prove that if the BH, QH, or QH|| collapses, for instance, if DP=co-DP or if PNP[k]=PNP[k+1], then there exists a sparse set S such that co-NP $\subseteq NPS, and therefore the PH collapses to PNPNP[logn], a subclass of the Δ3P level of the PH. Hence the structure of unsatisfiable Boolean formulas, co-NP, and the whole PH are all closely related to the structure of the BH and to the issue of how deterministic polynomial time algorithms can access the information from NP oracles.

Journal / Series

Volume & Issue



Date Issued



Cornell University


computer science; technical report


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record