부분 결과서지만 확인
Exponential Lower Bounds for Polytopes in Combinatorial OptimizationSamuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf · 2015Journal of the ACM 62(2), 2015 (논문별 쪽 1–23) · 학회 발표 STOC 2012 (Proceedings of the 44th Annual ACM Symposium on Theory of Computing), 95–106쪽 — 학회판 제목은 「Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds」 · arXiv:1111.0837외판원 다면체로 사영되는 다항 크기 선형 계획은 대칭 조건을 빼더라도 없음을 증명한 논문이다. Yannakakis 가 20년 전에 낸 문제(yannakakis-1991)의 해결이다. 「외판원 문제를 다항 크기 선형 계획으로 적어 P = NP 를 증명했다」는 유형의 주장이 어떤 형태로도 성립할 수 없음을 뜻하므로, 2-5 가 실패한 증명 시도의 한 갈래를 설명할 때 인용한다.
확인:학술지판과 학회판은 Crossref 등록 기록으로(학회판 제목은 등록 기록의 제목·부제와 arXiv 주석이 일치), 초록은 Crossref 와 arXiv 초록 페이지로 확인했다.