Research Initiation: Investigations into the Structure of Intractable Sets

点击翻译按钮获取中文摘要

This project is an investigation of the computational complexity of intractable sets. The object is to gain new insight into the rich mathematical structure that individual classes such as NP, EXP and TIME (2poly) appear to have, and to increase our understanding of the structural relationship between these classes. To these ends new concepts and proof techniques will be employed. Sets that are difficult to compute on almost all arguments play an important role in the structural analysis of complexity classes. Separation results between various deterministic, nondeterministic, and generalized Kolmogorov complexity classes can be witnessed by these sets. In cases where absolute results are elusive, relativization results will be achieved. Application of these results will be used to study the structure of complete sets in NP and EXP. A new nonconstructive reducibility that relates the polynomial complexity of computable sets will be used to investigate the structure of the classes NP and EXP. New results and insights into the fine structure of these classes have been obtained; further research into these areas is proposed.