We attain two main objectives in this thesis. First, we employ test languages to prove limitations of proof techniques to resolve certain questions in complexity theory. In this part of the thesis, we study the relationship between quantum classes and counting classes via closure properties, collapses, and relativized separations. We show that the best known classical bounds for quantum classes such as EQP and BQP cannot be significantly improved using relativizable proof techniques. In some cases, we strengthen known relativized separations between quantum and counting classes to their relativized immunity separations. Furthermore, using the closure properties of certain gap-definable counting classes, we prove strong consequences, in terms of the complexity of the polynomial hierarchy, of the following hypotheses: NQP is contained in BQP, and EQP equals NQP. Aside from using test languages to study the relationship between quantum and counting classes, we use test languages to construct, via degree bounds of polynomials, relativized worlds that exhibit separations of classes and nonexistence of complete sets.; Second, we study certain concrete problems and characterize their complexity either by showing completeness results for complexity classes or by relating their complexity to some well-studied computational problem (e.g., the graph isomorphism problem). In this part of the thesis, we study concrete problems related to the reconstruction of a graph from a collection of vertex-deleted or edge-deleted subgraphs, and concrete problems related to a notion of linear connectivity in directed hypergraphs. We show that the problems we study related to the reconstruction of graphs either are isomorphic (in complexity-theoretic sense) to the graph isomorphism problem or are many---one hard for the graph isomorphism problem. In our study related to directed hypergraphs, we introduce a notion of linear hyperconnectivity, denoted by L-hyperpath, in directed hypergraphs and show how this notion can be used to model problems in diverse domains. We study problems related to the cyclomatic number of directed hypergraphs with respect to L-hypercycles (the minimum number of hyperedges that need to be deleted so that the directed hypergraph becomes free of L-hypercycles) and obtain completeness results for different levels of the polynomial hierarchy.
展开▼
