Skip to main content
added 465 characters in body
Source Link
Noam
  • 9.4k
  • 48
  • 58

The existence of problems in DTIME(2^O(n)) which require exponential-size circuits to compute implies PRGs(which is the assumption in IW) seems plausible since otherwise we would have non-uniformity giving a speedup on EVERY computational problem -- which imply P=RP=BPP, by Impagliazzogoes completely against the current thinking that does not see a "too significant" gap between uniform and non-Wigderson:uniform complexity for "normal" problems. This thinking comes from the fact that there are very few examples where a "non-uniform" algorithm is known that is significantly better than the known uniform one http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf(again except for derandomization).

Another piece of "evidence" is that relative to a random oracle we do have P=BPP.

The existence of problems in DTIME(2^O(n)) which require exponential-size circuits to compute implies PRGs which imply P=RP=BPP, by Impagliazzo-Wigderson: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf

The existence of problems in DTIME(2^O(n)) which require exponential-size circuits to compute (which is the assumption in IW) seems plausible since otherwise we would have non-uniformity giving a speedup on EVERY computational problem -- which goes completely against the current thinking that does not see a "too significant" gap between uniform and non-uniform complexity for "normal" problems. This thinking comes from the fact that there are very few examples where a "non-uniform" algorithm is known that is significantly better than the known uniform one (again except for derandomization).

Another piece of "evidence" is that relative to a random oracle we do have P=BPP.

Source Link
Noam
  • 9.4k
  • 48
  • 58

The existence of problems in DTIME(2^O(n)) which require exponential-size circuits to compute implies PRGs which imply P=RP=BPP, by Impagliazzo-Wigderson: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf