지수 시간 가설은 틀렸다
OpenAI 명의의 논문은 임의의 고정 절 너비 k에 대해 k-CNF의 만족 할당 수를 결정론적 부분지수 시간과 다항 공간으로 정확히 계산하는 알고리즘을 제시합니다. 이 결과가 성립하면 ETH와 SETH를 비롯한 여러 계산 복잡도 가설이 반박되지만, 일반 NP 문제 전체에 부분지수 알고리즘이 생기는 것은 아닙니다.
AI 모델 · 최신기사
모델 공개와 성능, 가중치와 이용 조건을 다룹니다.
Anthropic 내부 Claude 연구 모델도 10월 16일 지수 시간 가설을 독자적으로 반박했습니다. 출력 토큰 1,400만 개, 인간 개입은 없었습니다
Anthropic의 내부 Claude 연구 모델이 3-SAT의 지수 시간 가설(ETH)을 반박하는 결과를 냈으며, 더 어려운 #3-SAT 계수 문제도 준지수 시간에 푸는 알고리즘을 제시합니다. Lean 4 형식화와 별도 커널 검증 절차도 공개했지만, 결과는 점근적이며 실제 문제 풀이 성능을 뜻하지 않습니다.
최근 제안된 o(n log n) 정수 곱셈 알고리즘
정수 곱셈의 기존 O(n log n) 시간 경계를 처음으로 o(n log n)으로 낮췄다는 알고리즘을, 기존 알고리즘의 저자인 David Harvey가 검토합니다. 직접 증명을 완전히 확인하지는 못했지만 AI의 설명을 바탕으로 주장이 그럴듯하다고 판단하며, 가속화 아이디어와 검증의 과제를 설명합니다.
몬테카를로 시뮬레이션
몬테카를로 시뮬레이션은 무작위 표본과 큰 수의 법칙을 활용해 적분, 조합 문제, 은퇴 자금의 불확실성을 추정합니다. 글은 원주율 추정과 SET 카드 조합 사례를 거쳐 평균 수익률만 적용한 은퇴 계산이 실제 위험을 가릴 수 있음을 보여줍니다.