확산 모델은 $p(x)$ 분포에서 학습하고 샘플링하는 데 매우 효과적인 방법입니다. 사후 샘플링에서는 측정 모델 $p(y \mid x)$와 측정값 $y$가 주어지면 $p(x \mid y)$에서 샘플링하려고 합니다. 사후 샘플링은 인페인팅, 초해상도, MRI 재구성과 같은 작업에 유용하며, 따라서 최근 연구에서 이를 휴리스틱하게 근사하는 알고리즘을 제시했지만 다항 시간 내에 올바른 분포로 수렴하는 것으로 알려진 것은 없습니다. 본 논문에서는 사후 샘플링이 계산적으로 다루기 어렵다는 것을 보여줍니다. 암호학의 가장 기본적인 가정인 일방향 함수가 존재한다는 가정 하에, 무조건적인 샘플링은 입증된 속도를 갖지만, 모든 알고리즘이 초다항 시간을 차지하는 예시가 존재합니다. 또한, 지수 시간 거부 샘플링 알고리즘은 역변환에 지수 시간이 걸리는 일방향 함수가 있다는 더 강력한 그럴듯한 가정 하에서 본질적으로 최적입니다.
