Key points are not available for this paper at this time.
D.S. Johnson 외의 정의에 따른 국소 탐색 문제의 한 클래스인 PLS(다항 시간 국소 탐색)가 고려된다(참조: J. Comput. Syst. Sci., vol.37, no.1, p.79-100 (1988)). PLS는 NP 문제의 유효한 해와 이웃 수준에서 많은 구조를 포착한다. 먼저 CNF(정규 곱셈 형태) 충족 가능성이 PLS-완전함이 보여지며, 동시에 제한된 크기의 절과 제한된 변수 발생 수에서도 마찬가지이다. 이 결과는 k-opt 이웃에서의 외판원 문제도 PLS-완전함을 보여주기 위해 사용된다. PLS-완전함이 NP-완전 문제의 일반적 행동이라는 주장이 제기된다.
Mark W. Krentel (Sun,)이 이 질문을 연구하였다.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: