Główne błędy w zaakceptowanych dokumentach FOCS / STOC [zamknięte]

Czy w przeszłości zdarzyło Ci się spotkać taką okazję? Cóż, istnieje możliwość na wszystko, ale chciałbym wiedzieć, jak realistyczna może być ta częstość. Mam na myśli poważne błędy zmieniające cel artykułu, a nie pomniejsze błędy, oczywiście. Dzięki

• Jednym z przypadków jest praca STOC '88 Blum-Feldman-Micali . Na usterkę zwrócił uwagę Mihir Bellare (prywatna komunikacja). Odpowiednią dyskusję znajdziesz tutaj .

• Petri net osiągalności Problem ma bogatą historię, gdzie niekompletne lub wadliwe dowody później prowadzić do nowych rezultatów. GS Sacerdote i RL Tenney przedstawili niekompletny dowód rozstrzygalności na STOC '77 , który jednak miał zasadnicze znaczenie w późniejszym dowodzie EW Mayr na STOC '81 i jego poprawie przez SR Kosaraju na STOC '82 . Te dowody rozstrzygalności nie miały górnego limitu złożoności (stosują dobrze quasi-porządki do zakończenia). Z. Bouziane później twierdził, że znalazł algorytm 2ExpSpace na FOCS '98 . Usterkę wskazał P. Jančar (i ostatecznie opublikował w notatce), ale praca Bouziane pomogła odnowić zainteresowanie tym starym pytaniem. Chociaż wciąż nie są znane górne granice złożoności tego problemu, J. Leroux przedstawił niedawno nowy dowód rozstrzygalności na POPL '11 .

Nie w STOC / FOCS:

Kolejny przypadek miał miejsce podczas konferencji Structure in Complexity Theory (1988) (jeśli się nie mylę, teraz nazywa się Konferencja złożoności obliczeniowej). Tytuł artykułu brzmiał : Potęga interaktywnych protokołów o wielu mocach . Dwa lata później autorzy (Fortnow, Rompel i Sipser) opublikowali na tej samej konferencji dwustronicowy artykuł „Errata for On Power of Multi-Prover Interactive Protocols”. Niestety IEEE nie oferuje tego papieru do pobrania.