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.