부분 결과서지만 확인
Time-space lower bounds for satisfiabilityLance Fortnow, Richard Lipton, Dieter van Melkebeek, Anastasios Viglas · 2005Journal of the ACM 52(6), 835–865쪽 (2005)황금비보다 작은 상수 c 마다, 시간 n^c 와 n 의 작은 거듭제곱 공간만 쓰는 결정적 기계로는 SAT 를 풀 수 없음을 보인 논문이다. 초록은 일반적인 계산 모형에서 SAT 에 대한 첫 다항식 꼴 시간·공간 하한이라고 적는다. 증명 방식은 가정을 세워 위계 정리와 모순을 끌어내는 간접 대각선 논법이다. SAT 하한의 현황을 인용하는 글의 표준 출전이다.
확인:Crossref 의 DOI 등록 기록으로 제목·저자·권호·쪽을 확인하고 같은 기록의 초록을 읽었다.