콜모고로프 복잡도

문자열 x 를 출력하는 가장 짧은 프로그램의 길이를 x 의 콜모고로프 복잡도라 한다. 「01 을 천 번 반복」처럼 규칙이 있는 문자열은 값이 작고, 무작위 문자열은 자기 자신을 그대로 적는 것보다 줄일 수 없어 값이 크다. 이 값을 계산하는 알고리즘은 존재하지 않는다(결정 불가능). 프로그램의 실행 시간에 한도를 둔 변형은 계산할 수 있고 NP 와 관련되며, 그 어려움을 묻는 문제들이 MCSP 와 함께 메타 복잡도의 연구 대상이다.