# Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy

## No Access Until

##### Permanent Link(s)

## Collections

## Other Titles

## Author(s)

## Abstract

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