Average-case complexity and instance complexity
Date
2000
Authors
Srinivasan, Sridhar
Major Professor
Advisor
Lutz, Jack H.
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis characterizes the set of problems that are decidable in average polynomial time in terms of the instance complexities of their individual instances. Different approaches are investigated and the relationships among them are shown. It is shown that almost every instance of almost every problem in exponential time has essentially maximal instance complexity. Using these results, it is shown that the set of problems decidable in average polynomial time with respect to a particular probability distribution has measure 0 in exponential time.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
thesis