1-3
평균적 복잡도
average-case complexity
가장 고약한 입력이 아니라 「보통의」 입력에서 문제가 얼마나 어려운지
입력이 어떤 확률 분포에서 뽑힐 때 대부분의 입력을 빨리 풀 수 있는지를 따진다(평균 경우 복잡도라고도 한다). P 대 NP 는 최악의 경우에 관한 질문이어서, P ≠ NP 이더라도 NP 문제가 대부분의 입력에서는 쉬울 수 있다. 암호가 안전하려면 무작위로 만든 사례가 어려워야 하므로 평균적 어려움이 필요하다. NP 문제의 최악의 경우 어려움에서 평균적 어려움을 끌어낼 수 있는지는 미해결이고, 히라하라의 2018년 결과 등이 그 방향의 부분적 진전이다.