Complexity of Feasible Computations

Suny At Buffalo, Amherst NY

Investigators

Abstract

This project continues research on the computational complexity of feasible computations, with the larger goal being to distinguish complexity classes that contain feasibly computable problems from those that do not. The emphasis is to continue investigation into fundamental areas of computational complexity theory. The project advances research on disjoint NP pairs. Disjoint NP pairs are technically equivalent to promise problems, and they were studied previously because of their relevance to security issues in cryptography. This project investigates their relevance to propositional proof systems, and solves problems that add insight to questions about proof systems. The project continues to investigate multivalued functions as a model of computation. Whereas it has been common practice to study the complexity of computational problems by focusing on decision problems alone, it is frequently more natural to study the computational complexity of problems directly as multivalued partial functions. Average-case complexity theory provides a framework for the classification of problems according to average-case analyses. This project continues to develop the theory of average-time complexity, for the average-case complexity of a problem is frequently a more important measure than its worst-case complexity. Regarding the broader impact of this activity, the PI offers advanced graduate courses and seminars that include the results of this project. The PI's graduate students participate fully in the activities of this project. All results are disseminated broadly. Results are submitted to major scientific symposia and to refereed journals