소수 판별

수 N 이 소수인지 묻는 결정 문제다. 아그라왈·카얄·삭세나가 2002년에 무작위를 쓰지 않는 다항 시간 알고리즘(AKS)을 내놓아 P 에 속함이 증명되었다. 그전에도 무작위를 쓰는 빠른 방법은 알려져 있었다. 합성수임을 아는 것과 그 약수를 실제로 찾는 것(인수분해)은 다른 문제다. 오래 어렵다고 여겨진 문제가 뜻밖에 P 로 밝혀진 사례로, 「알고리즘을 못 찾았다」가 「알고리즘이 없다」의 증거는 아님을 일깨운다.