Details

Autor(en) / Beteiligte

• Buhrman, Harry
• Fortnow, Lance
• Pavan, A.

Titel

Some Results on Derandomization

Ist Teil von

• Lecture notes in computer science, 2003, p.212-222

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2003

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We show several results about derandomization including 1. If NP is easy on average then efficient pseudorandom generators exist and P = BPP. 2. If NP is easy on average then given an NP machine M we can easily on average find accepting computations of M(x) when it accepts. 3. For any A in EXP, if NEXPA is in PA/poly then NEXPA = EXPA. 4. If A is ⌆pk -complete and NEXPA is in PA/poly then NEXPA = EXP = MAA.