1-3
하한
lower bound
「어떤 방법으로도 이보다 적은 자원으로는 못 푼다」는 증명
문제를 푸는 데 반드시 드는 시간·공간·회로 크기의 아래쪽 한계다. 위쪽 한계(상한)는 알고리즘 하나를 내놓으면 증명되지만, 하한은 아직 아무도 떠올리지 못한 것까지 포함해 모든 알고리즘이 실패함을 보여야 한다. P ≠ NP 는 「NP-완전 문제에는 다항 시간을 넘는 하한이 있다」는 하한 명제다. 지금까지 증명된 하한은 AC⁰·단조 회로처럼 제한된 계산 모형에 대한 것이고, 제한 없는 모형에서는 매우 약한 것뿐이다.