탈무작위화

동전 던지기를 쓰는 알고리즘을, 느려지는 정도를 다항식 안으로 묶으면서 무작위 없이 돌아가게 바꾸는 것이다. 임팔리아초와 위그더슨은 1997년에, 지수 시간(2^O(n))에 풀리는 문제 가운데 지수 크기의 회로가 필요한 것이 하나라도 있으면 P = BPP 임을 보였다. 곧 회로 하한을 증명하면 무작위를 없앨 수 있고, 거꾸로 무작위를 없애는 일도 일종의 회로 하한을 요구한다는 것이 알려져 있다. 알고리즘을 설계하는 문제와 하한을 증명하는 문제가 맞닿아 있음을 보여 주는 주제다.