AVERAGE CASE COMPLEXITY THEORY

Average case complexity is a branch of computational complexity theory that is focused on analyzing the average resource usage of computational problems over the distribution of inputs. In this research paper, we focus on Leonid Levin’s theory of average case complexity. This paper will investigate average case problems as distributional problems and attempt to produce an analogue of results in worst case complexity theory in the average case.