자연 증명

라즈보로프와 루디치가 1994년에 발표한 개념이다. 알려진 회로 하한 증명은 대개 「쉬운 함수는 갖지 못하는 성질」을 찾아내는데, 그 성질이 (1) 함수의 진리표를 보고 효율적으로 판정할 수 있고(구성적) (2) 무작위로 고른 함수 가운데 상당수가 가지면(큼) 자연스럽다고 한다. 두 사람은 충분히 강한 유사난수 함수가 존재한다면 자연스러운 성질로는 P/poly 에 대한 하한, 곧 P ≠ NP 를 증명할 수 없음을 보였다. 그런 성질은 유사난수 함수와 진짜 무작위 함수를 구별하는 데 쓰일 수 있기 때문이다. 어려운 문제가 존재한다는 바로 그 가정이 어려움을 증명하는 길을 막는 셈이다.