과거에 그런 일이 있었습니까? 글쎄, 모든 것에 대한 가능성이 있지만이 발병률이 얼마나 현실적인지 알고 싶습니다. 물론 논문의 목표를 바꾸는 심각한 실수와 사소한 실수는 아닙니다. 감사
답변
-
한 예로 Blum-Feldman-Micali의 STOC ’88 paper가 있습니다. 이 결함은 Mihir Bellare (개인 통신)에 의해 지적되었습니다. 여기 에서 관련 토론을 찾을 수 있습니다 .
-
페트리 네트 접근 가능성의 문제는 불완전하거나 결함이 증거 나중에 새로운 결과로 이어질 풍부한 역사를 가지고 있습니다. GS Sacerdote와 RL Tenney는 STOC ’77 에서 불완전한 결정 성 증명을 발표 했지만 STOC ’81 에서 EW Mayr의 증거 와 STOC ’82 에서 SR Kosaraju의 개선에 중요한 역할을 했습니다 . 이러한 결정 가능성 증명에는 복잡성 상한선이 포함되지 않았습니다 ( 종료를 위해 유사 준 순서 를 사용함 ). Z. Bouziane은 나중에 FOCS ’98 에서 2ExpSpace 알고리즘을 발견했다고 주장했다 . 결함이 P. Jančar에 의해 지적 (그리고 마지막에 발표 된 주), 그러나 Bouziane의 연구는이 오래된 질문에 대한 관심을 새롭게하는 데 도움이되었습니다. 이 문제의 복잡성에 대한 알려진 상한은 아직 없지만 J. Leroux는 최근 POPL ’11 에서 새로운 결정 가능성 증명을 발표했습니다 .
STOC / FOCS에 없음 :
또 다른 경우는 Structure in Complexity Theory (1988) 회의에서 발생했습니다 (실수하지 않으면 지금은 전산 복잡성 회의라고합니다.)이 논문의 제목은 다중 전력 대화 형 프로토콜의 힘에 관한 것 입니다. 2 년 후, 저자 (Fortnow, Rompel 및 Sipser)는 같은 회의에서 두 페이지의 논문 “다발성 대화 형 프로토콜의 힘에 대한 에라타”를 발표했습니다. 불행하게도 IEEE는이 문서를 다운로드 용으로 제공하지 않습니다.