부분 결과원문 확인
Some optimal inapproximability resultsJ. Håstad · 2001Journal of the ACM 48(4), 798–859쪽 (2001) · 학회 발표 STOC 1997, 1–10쪽MAX-3SAT 을 비롯한 여러 문제에 대해 더는 좁힐 수 없는 근사 불가능성 문턱을 증명한 논문이다. 충족 가능한 3SAT 식에서 절의 7/8 보다 조금이라도 많은 비율을 늘 충족시키는 다항 시간 알고리즘이 있으면 P = NP 임을 보인다. 2-4 의 부분 결과 개관과 PCP 정리 글이 인용한다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 초록을 읽음.원문 주소 (www.csc.kth.se)이 카드를 붙인 자료 2