부분 결과원문 확인
Non-black-box worst-case to average-case reductions within NPShuichi Hirahara · 2018FOCS 2018 (59th Annual IEEE Symposium on Foundations of Computer Science), 247–258쪽 · ECCC TR18-138 (2018)NP 안의 문제에 대해, 블랙박스 방식의 한계를 넘는 「최악의 경우에서 평균적 경우로」의 환산을 처음 제시한 논문이다. 시간 제한을 둔 콜모고로프 복잡도와 최소 회로 크기를 근사하는 문제가 평균적으로 쉽다면 최악의 경우에도 쉽다는 것을 보인다. 메타 복잡도 접근의 대표 성과로, 평균적 복잡도와 다섯 세계를 공부하는 전문 독자에게 권한다. ECCC 공개본으로 연결한다.
확인:ECCC 공개본(TR18-138)의 초록과 서론(§1.1)을 읽음.원문 주소 (eccc.weizmann.ac.il)이 카드를 붙인 자료 4