Towards a Theory of Average Case Complexity
| Title | Towards a Theory of Average Case Complexity |
| Publication Type | Technical Report |
| Year of Publication | 1989 |
| Authors | Ben-David, S., Chor B., Goldreich O., & Luby M. |
| Other Numbers | 503 |
| Abstract | This paper takes the next step in developing the theory of average case complexity, a study initiated by Levin. Previous works have focused on the existence of complete problems [Le,Gu,VL]. We widen the scope to other basic questions in computational complexity. For the first time in the context of average case complexity, we show the equivalence of search and decision problems, analyze the structure of NP under P reductions, and relate the NP versus average-P to non-deterministic versus deterministic (worst case) exponential time. We also present definitions and basic theorems regarding other complexity classes, such as average log-space. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-89-004.pdf |
| Bibliographic Notes | ICSI Technical Report TR-89-004 |
| Abbreviated Authors | S. Ben-David, B. Chor, O. Goldreich, and M. Luby |
| ICSI Publication Type | Technical Report |