알고리즘서지만 확인
A probabilistic algorithm for k-SAT and constraint satisfaction problemsUwe Schöning · 1999FOCS 1999 (40th Annual Symposium on Foundations of Computer Science), 410–414쪽 · 학술지판 Algorithmica 32(4), 615–623쪽 (2002) — 학술지판 제목은 「A Probabilistic Algorithm for k-SAT Based on Limited Local Search and Restart」무작위 배정에서 출발해 어긋난 절의 변수를 뒤집기를 되풀이하는 단순한 무작위 알고리즘으로 3-SAT 를 약 (4/3)ⁿ 시간에 푼다는 결과로 널리 인용된다. 2ⁿ 전수 탐색보다 지수의 밑을 낮춘 대표적인 예다. 밑을 1 에 얼마든지 가깝게 낮출 수 있느냐가 지수 시간 가설(impagliazzo-paturi-2001)의 물음이다.
확인:학회판과 학술지판(DOI 10.1007/s00453-001-0094-7)은 Crossref 등록 기록으로 확인했다. 학회판 기록의 저자 이름 머리글자가 잘못 올라 있어 저자 이름은 Crossref 에 등록된 다른 책의 참고문헌 기록으로 확인했다.