Login
Computer Science @ Rochester
Monday, July 19, 2004
11:00 AM
CSB 209
Kumar Mayur Thakur
University of Rochester
General Tools for Determining Problem Complexity
Programmers, computer science researchers, and engineers need to determine the computational complexity of problems on a near-daily basis, and they typically ask the following questions: Is there an efficient algorithm for the problem? Is the problem hard? If so, how hard is the problem? Are there large subclasses of problems that are easy?

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.