Apakah derandomisasi kelas yang sedikit tidak seragam, misalnya BPP / linear, telah dipelajari?

10

Dengan BPP / linear saya merujuk ke mesin BPP dengan saran linier, yang memenuhi janji ketika diberi saran "benar", dan derandomisasi harus memberi kita, katakanlah, algoritma P / linear atau (SUBEXP / linear).

Jika kita menggunakan asumsi yang tidak seragam, saya pikir hasil klasik akan berhasil, karena kita bisa "menipu" musuh yang tidak seragam.

Namun, dengan menggunakan asumsi yang seragam, katakanlah , derandomisasi non-sepele sepertinya merupakan pertanyaan yang lebih sulit.EXPBPP

Apakah ada hasil mengenai jenis kelas ini, tidak perlu BPP / linear?

Sebastian Ben Daniel
sumber

Jawaban: