P≠NP보다 강력한 결과를 증명했다고 주장하는 논문이 Springer Nature의 Frontiers of Computer Science 저널에 게재되어 논란을 일으켰습니다. 저자 중 한 명은 해당 저널의 부편집장입니다. 컴퓨터 과학자 Ryan Williams와 Eric Allender는 이 논문의 증명에 심각한 결함이 있으며, 알려진 알고리즘과도 모순됨을 발견했습니다. 그들은 논문 철회를 요구하는 의견을 제출했지만, 편집장은 거부하고 수정된 의견만 게재하는 것에 동의했습니다. 이 사건은 저널의 동료 심사 과정에 심각한 문제점을 드러내고, 저널의 명성에 대한 우려를 높이고 있습니다. 이는 기술 뉴스입니다.
더 보기
2025년 괴델상은 Eshan Chattopadhyay와 David Zuckerman의 획기적인 논문 “명시적 이원 추출기와 복원력 있는 함수”에 수여되었습니다. 이 논문은 STOC 2016과 Annals of Math 2019에 게재되었으며, 람제이 그래프 구성을 크게 개선하여 기존 방법을 훨씬 뛰어넘는 지수적 한계를 달성했습니다. 이 성과는 비결정론 제거에 대한 영향과 람제이 이론에 대한 놀라운 응용으로 높이 평가되고 있으며, 의사 난수성과 조합론에서의 이중적 의미에 대한 논의를 불러일으키고 있습니다.
더 보기
획기적인 연구 결과가 알고리즘 시뮬레이션의 기반을 뒤흔들었습니다. Ryan Williams의 새로운 연구는 모든 알고리즘을 원래 실행 시간보다 훨씬 적은 메모리를 사용하여 시뮬레이션할 수 있음을 보여줍니다. 이는 이전 최고 결과를 훨씬 뛰어넘는 개선입니다. 이 돌파구는 Cook과 Mertz의 공간 효율적인 트리 평가 알고리즘을 활용하여 튜링 머신 계산을 영리하게 분할하고 유한체 인코딩을 사용하여 공간 복잡도를 거의 2배로 개선합니다. 시간 제한은 유지되지 않지만, 이 획기적인 결과는 복잡도 이론에 큰 영향을 미치며 공간 복잡도 상한의 추가 감소 등 미래 연구의 길을 열어줍니다. P와 PSPACE 복잡도 클래스의 분리로 이어질 가능성도 있습니다.
더 보기