Complexity of Feasible Computations

该项目继续研究可行计算的计算复杂性，其更大的目标是区分包含可行计算问题的复杂性类别和不包含可行计算问题的复杂性类别。重点是继续研究计算复杂性理论的基本领域。该项目推进了不相交NP对的研究。不相交的NP对在技术上等同于承诺问题，因为它们与密码学中的安全问题相关，所以以前对它们进行了研究。该项目调查了它们与命题证明系统的相关性，并解决了一些问题，这些问题增加了对证明系统问题的洞察力。该项目继续研究作为计算模型的多值函数。虽然研究计算问题的复杂性通常只关注决策问题，但将问题的计算复杂性直接作为多值偏函数来研究往往更为自然。平均情况复杂性理论为根据平均情况分析对问题进行分类提供了一个框架。这个项目继续发展平均时间复杂度理论，因为一个问题的平均情况复杂度通常是比最坏情况复杂度更重要的度量。关于这项活动的更广泛的影响，PI提供高级研究生课程和研讨会，其中包括该项目的成果。PI的研究生充分参与该项目的活动。所有结果都广泛传播。结果提交给主要的科学研讨会和评审期刊

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