## Abstract

We prove several results about the average-case complexity of problems in the Polynomial Hierarchy (PH). We give a connection among average-case, worst-case, and non-uniform complexity of optimization problems. Specifically, we show that if PNP is hard in the worst-case then it is either hard on the average (in the sense of Levin) or it is non-uniformly hard (i.e. it does not have small circuits).

Recently, Gutfreund, Shaltiel and Ta-Shma (IEEE Conference on Computational Complexity, 2005) showed an interesting worst-case to average-case connection for languages in NP, under a notion of average-case hardness defined using uniform adversaries. We show that extending their connection to hardness against quasi-polynomial time would imply that NEXP doesn’t have polynomial-size circuits.

Finally we prove an unconditional average-case hardness result. We show that for each k, there is an explicit language in P TeX which is hard on average for circuits of size n k .

Recently, Gutfreund, Shaltiel and Ta-Shma (IEEE Conference on Computational Complexity, 2005) showed an interesting worst-case to average-case connection for languages in NP, under a notion of average-case hardness defined using uniform adversaries. We show that extending their connection to hardness against quasi-polynomial time would imply that NEXP doesn’t have polynomial-size circuits.

Finally we prove an unconditional average-case hardness result. We show that for each k, there is an explicit language in P TeX which is hard on average for circuits of size n k .

Original language | English |
---|---|

Title of host publication | FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science |

Subtitle of host publication | 26th International Conference, Kolkata, India, December 13-15, 2006, Proceedings |

Publisher | Springer Berlin Heidelberg |

Pages | 188-199 |

Number of pages | 12 |

Volume | 4337 |

ISBN (Electronic) | 978-3-540-49995-4 |

ISBN (Print) | 978-3-540-49994-7 |

DOIs | |

Publication status | Published - 2006 |