This thesis has four central components. First, we investigate concrete problems related to the notion of hyperpaths and hypercycles in directed hypergraphs, and prove completeness results for different levels of the polynomial-time hierarchy. Second, we investigate concrete problems related to the reconstruction of a graph from a collection of vertex-deleted or edge-deleted subgraphs, and prove that many of these problems are isomorphic (as in complexity-theoretic sense) to the Graph Isomorphism problem. Third, we employ test languages---languages uniformly parameterized by sets---to study the relationship between quantum and classical complexity classes by means of relativized separations, collapses, and closure properties. Fourth, we employ test languages to exhibit the applicability of the polynomial degree bound technique to notions such as relativized nonexistence of Turing hard sets, (non)uniform gap-definability, and relativized separations.
In this talk, due to time limitations, I will focus just on the relationship between quantum and classical complexity classes. We study the complexity of the quantum classes EQP, BQP, and NQP (quantum analogs of P, BPP, and NP, respectively) using the classical complexity classes ZPP, WPP, and C_{=}P. First, we construct a relativized world where ZPP is not contained in WPP. As a consequence, this implies that no relativizable proof technique can significantly improve the best known classical upper bound for BQP and the best known classical lower bound for EQP. Second, we extend some of the known relativized separations of quantum classes from classical classes to relativized immunity separations between these classes. Third, we investigate the reduction closure properties of the classical classes WPP and AWPP, and use these closure properties to prove strong consequences, in terms of the complexity of the polynomial-time hierarchy, of the following hypotheses: (1) NQP is contained in BQP, and (2) NQP equals EQP. Our results provide a better understanding of the relationship between quantum and classical complexity classes.