다섯 세계

임팔리아초가 1995년 글에서 제시한 분류다. 알고리스미카(Algorithmica)는 P = NP 이거나 그에 준하는 세계, 휴리스티카(Heuristica)는 NP 문제가 최악의 경우에는 어렵지만 평균적으로는 쉬운 세계, 페실란드(Pessiland)는 평균적으로 어려운 문제는 있지만 일방향 함수는 없는 세계, 미니크립트(Minicrypt)는 일방향 함수는 있지만 공개키 암호는 불가능한 세계, 크립토매니아(Cryptomania)는 공개키 암호가 가능한 세계다. 우리가 어느 세계에 사는지는 증명되지 않았다. 많은 연구자가 크립토매니아라고 믿지만, 그것을 증명하면 P ≠ NP 도 함께 증명되므로 적어도 P ≠ NP 만큼 어려운 일이다.