Moser, Philippe (2002) ZPP is Hard Unless RP is Small. Electronic Colloquium on Computational Complexity (15). ISSN 1433-8092
Preview
PM-ZPP-2002.pdf
Download (207kB) | Preview
Abstract
We use Lutz's resource bounded measure theory to prove that, either RP is
small, or ZPP is hard. More precisely, we prove that if RP has not p-measure zero, then
EXP equals ZPP on infinitely many input lengths, i.e. there are infinitely many input lengths on which ZPP is hard. Second we prove that if NP has not p-measure zero, then derandomization of AM is possible on infinitely many input length, i.e. there are infinitely many input lengths such that NP = AM. Finally we prove easiness versus randomness tradeoffs for classes in the polynomial time hierarchy.
We show that it appears to every strong adversary that either,
every Ʃᴾᵢ algorithm can be simulated infinitely often by a subexponential
co-nondeterministic time algorithm, having oracle access to Ʃᴾᵢ -2 , or BP Ʃᴾᵢ = Ʃᴾᵢ .
Item Type: | Article |
---|---|
Keywords: | derandomization; ZPP; RP; |
Academic Unit: | Faculty of Science and Engineering > Computer Science |
Item ID: | 8248 |
Depositing User: | Philippe Moser |
Date Deposited: | 29 May 2017 14:33 |
Journal or Publication Title: | Electronic Colloquium on Computational Complexity |
Publisher: | Weizmann Institute of Science |
Refereed: | No |
Related URLs: | |
URI: | https://mural.maynoothuniversity.ie/id/eprint/8248 |
Use Licence: | This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here |
Repository Staff Only (login required)
Downloads
Downloads per month over past year