M.S. Thesis Defense - S. G. Krishnasamy

Date: 17 Nov, 2009
Time: 10:10 AM
Location: 217 Atanasoff Hall
Topic: Complexity Cores in Average-case Complexity Theory
Major Professor(s): Pavan Aduri


Abstract:

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 is not equal to 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 is not equal to 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.