It is desirable to have easily applied tools (theorems, classification tests, complete characterizations, etc.) that in one fell swoop classify a large class of problems in the domain of interest. This thesis provides such general tools for determining the complexity of problems arising in the following settings: Boolean circuits, language properties of central complexity classes (such as NP, PP, and ParityP), cycles in graphs, oracle (database) access, theoretical models of computer simulation, and structural restrictions on the witness functions of nondeterministic polynomial-time Turing machines.
This talk will describe one of the several classification tools from the thesis. This tool, a complexity-theoretic analog of Rice's Theorem from recursive function theory, classifies properties of Boolean circuits. We obtain the strongest known Rice-style theorem for a broad class of properties of Boolean circuits, and show that this result cannot be much improved using relativizable techniques. We also establish a generalized complexity-theoretic Rice-style theorem that holds for language properties of many important problem classes.