부분 결과서지만 확인
On Worst-Case to Average-Case Reductions for NP ProblemsA. Bogdanov, L. Trevisan · 2006SIAM Journal on Computing 36(4), 1119–1159쪽 (2006) · 학회 발표 FOCS 2003, 308–317쪽NP 문제의 최악의 경우 난해성을 평균적 난해성으로 옮기는 비적응적 환원이, 다항 위계가 무너지지 않는 한 불가능함을 보인 논문이다. Feigenbaum–Fortnow 의 결과를 잇는다. 2-3 의 평균적 복잡도 글이 「세계 사이의 벽을 허물기 어려운 까닭」으로 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Bogdanov–Trevisan 개관(2006) §1.1.6 으로 확인.