접근서지만 확인
Power from Random StringsEric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger · 2006SIAM Journal on Computing 35(6), 1467–1493쪽 (2006) · 학회 발표 FOCS 2002 (43rd Annual IEEE Symposium on Foundations of Computer Science), 669–678쪽콜모고로프 복잡도가 높은 문자열들의 집합을 오라클로 쓰면 PSPACE·EXP 같은 클래스의 문제를 풀 수 있음을 보인 논문이다. 새 시간 제한 콜모고로프 복잡도 KT 를 정의하고, 이산 로그·소인수분해·몇몇 격자 문제가 KT 가 높은 문자열의 집합을 오라클로 쓰는 무작위 다항 시간에 풀림을 보였다. KT 는 최소 회로 크기와 가깝게 이어진 척도로 알려져 있다. 2-3 의 메타 복잡도 글이 다루는 「압축할 수 없음을 판정하는 일의 어려움」의 기초 문헌이다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 확인하고 학술지판 기록의 초록을 읽었다.