Date of Award
Master of Science
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.
Gopalakrishnan Krishnasamy Sivaprakasam
Krishnasamy Sivaprakasam, Gopalakrishnan, "Complexity cores in average-case complexity theory" (2009). Graduate Theses and Dissertations. 11033.