Complexity cores in average-case complexity theory
Gopalakrishnan Krishnasamy Sivaprakasam · 2009
Complexity cores in average-case complexity theory In average-case complexity theory, one of the interesting questions is whether the existence of worst-case hard problems in NP implies the existence of problems in NP that are hard on average. In other words, `If P ≠NP then NP is not a subset of Average-P'. It is not known whether such worst-case to average-case connection exists for NP. However it is known that such connections exist for complexity classes such as EXP and PSPACE. This worst-case to average-case connections for classes such as EXP and PSPACE are obtained via random self-reductions. There is evidence that techniques used to obtain worst-case to average-case connections for EXP and PSPACE do not work for NP. In this thesis, we present an approach which may be helpful to establish worst-case and average-case connection for NP. Our approach is based on the notion of complexity cores. The main result is `If P ≠ NP and there is a language in NP whose complexity core belongs to NP, then NP is not a subset of Average-P'. Thus to exhibit a worst-case to average-case connection for NP, it suffices to show the existence of a language whose core is in NP.