Begränsa sökytan f0 1g n till uppsättningen av sanningstabeller av \ easy" Booleska funktioner på log n variabler, samt använda några kända hårdhet-randomness Tradeo s, vi etablera ett antal resultat som relaterar komplexiteten o f exponentiellt-tid och probabilistic polynomialtime komplexitet klasser. I synnerhet visar vi att NEXP P=poly, NEXP = MA detta kan tolkas som att säga att ingen derandomisering av MA (och därmed av löfte-BPP) är möjligt om NEXP innehåller en hård Boolesk funktion. Vi a l s o p r o ve flera nedåt stängningsresultat för ZPP, RP, BPP, och MA t.ex., vi s h o w EXP = BPP, EE = BPE, där EE är den dubbla exponentiella tidsklassen och BPE är den exponentiella tiden analog av BPP.
Man bör komma ihåg att NEXP  på P/poly på NEXP = MA REF.
In search of an easy witness: exponential time vs. probabilistic polynomial time
{'venue': 'J. Comput. Syst. Sci.', 'journal': 'J. Comput. Syst. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}