Complexity cores in average-case complexity theory

TL;DRAbstract

Complexity cores in average-case complexity theory\nIn average-case complexity theory, one of the interesting questions is\nwhether the existence of worst-case hard problems in NP implies the\nexistence of problems in NP that are hard on average. In other words, `If P\n≠NP then NP is not a subset of Average-P'. It is not known whether such\nworst-case to average-case connection exists for NP. However it is known\nthat such connections exist for complexity classes such as EXP and PSPACE.\nThis worst-case to average-case connections for classes such as EXP and\nPSPACE are obtained via random self-reductions. There is evidence that\ntechniques used to obtain worst-case to average-case connections for EXP and\nPSPACE do not work for NP.\nIn this thesis, we present an approach which may be helpful to establish\nworst-case and average-case connection for NP. Our approach is based on the\nnotion of complexity cores. The main result is `If P ≠ NP and there is a\nlanguage in NP whose complexity

Chat with Paper

AI Agents for this Paper