구분기를 여는 것: BPL=L을 위해 BPL의 특성을 사용하는 난이도 대 무작위성 접근법

우리는 공간 한정 계산의 비무작위화라는 오랜 문제를 해결하기 위한 난이도 대 무작위성 접근법의 잠재력에 대한 설득력 있는 증거를 제공합니다. 우리의 첫 번째 기여는 강력한 (하지만 일치하지 않는) 하한이 무조건적으로 입증될 수 있는 균일 결정론적 알고리즘 클래스에 대한 난이도 가정을 기반으로 한 유한 공간 기계의 비무작위화입니다. 우리는 BPL=L이 "평균적으로" 성립함을 보여주는 결과와 BPSPACEO(n)=DSPACEO(n)임을 보여주는 유사한 결과를 증명합니다. 다음으로 우리는 로그 공간에 대한 이전 작업의 주요 결과를 상당히 개선합니다. 우리의 결과 중 하나로, 우리는 최소 메모리 풋프린트를 가진 비무작위화에 필요한 가정을 완화합니다 (즉, 작은 상수 c에 대해 BPSPACES⊆ DSPACEc · S를 보여줍니다) — 이는 이전 작업에서 필요했던 암호화 가정을 완전히 제거함으로써 이루어졌습니다. 우리의 모든 결과를 뒷받침하는 주요 기여는 난이도 대 무작위성 결과를 증명할 때 공간 한정 튜링 기계의 설명을 비블랙박스 방식으로 사용하는 것입니다. 즉, 우리의 결과를 증명할 수 있도록 해주는 중요한 포인트는 공간 한정 기계에 특정한 속성을 사용한다는 것입니다.