2015/05/13 by Ilya Kapovich, Kapovich, Ilya
Computer Science · Mathematics · #68Q15 Secondary 20F #68Q17 #68Q25 #94A #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #Logic (math.LO) #Primary 03D15 #cs.CC #math.GR #math.LO #msc:03D15 #msc:20F #msc:68Q15 #msc:68Q17 #msc:68Q25 #msc:94A
paper · pdf · doi:10.48550/arxiv.1505.03218
9 pages, no figures
arxiv created 2015/05/13 · arxiv updated 2015/05/14
We propose a more general definition of generic-case complexity, based on using a random process for generating inputs of an algorithm and using the time needed to generate an input as a way of measuring the size of that input.