k-컬러링, 채색수 계산보다 빠르다
k-Coloring is Faster than Computing the Chromatic Number
n-정점 그래프에서 k-컬러링 문제를 (2−ε_k)^n 시간에 해결하는 무작위 알고리즘을 제시했다. 여기서 ε_k는 모든 고정 k에 대해 양수이다. 이전에는 k≤6인 경우에만 일반적인 O*(2^n) 알고리즘보다 빠른 해법이 알려져 있었다. 이 연구는 Zamir의 (k+2)-컬러링에서 k-리스트-컬러링으로의 축소와 하이퍼그래프 컨테이너 기법을 결합하고, 길고 짧은 색상 목록이 혼합된 리스트-컬러링 인스턴스를 위한 새로운 알고리즘을 개발하여, 고정 팔레트에서 (k+1)-리스트-컬러링을 k-리스트-컬러링으로 반복적으로 축소하는 방법을 확립했다.
이전에는 k≤6인 경우에만 일반적인 O*(2^n) 시간 알고리즘보다 빠른 해법이 알려져 있었다.
HN 토론
23- emil-lp
잘 모르는 사람들을 위해 설명하자면:
k-컬러링은 그래프를 k개의 색으로 칠하되 인접한 두 노드가 같은 색을 갖지 않도록 칠할 수 있는 성질을 말한다. k-컬러링 문제는 결정 문제, 즉 예/아니오 질문이다.
그래프의 채색수(chromatic number)는 k-컬러링이 가능한 가장 작은 k 값이다.
당연히, 하나에 대한 알고리즘이 있으면 다른 하나에 대한 알고리즘도 있다.
질문은: k-컬러링을 계산하는 것이 실제 최소 k 값, 즉 채색수를 계산하는 것보다 빠른가 하는 것이었다.
숲, 트리, 이분 그래프는 2-컬러링이 가능하다. 평면 그래프는 4-컬러링이 가능하다. 평면 그래프의 채색수가 3인지 확인하는 것은 NP-완전 문제이다.
매우 흥미로운 미해결 문제인 하드비거 추측(Hadwiger's conjecture)이 있는데, 이는 본질적으로 채색수가 클릭(마이너) 수와 같다고 말한다(그것이 무엇을 의미하든).
- black_knight
brev 논문의 끝부분에 LLM 사용에 관한 섹션이 있다.
이제 이 논문은 동료 검토를 거칠 것이다. 따라서 출판되면 우리는 그 결과를 수학의 다른 출판된 결과와 마찬가지로 신뢰하게 될 것이다. 그러나 인간도 오류에서 자유롭지 않지만, LLM은 확신에 차서 올바른 것처럼 보이는 내용을 내뱉는 경향이 있다. 그래서 이런 방식으로 증명을 생성하는 데 사용될 때 걱정이 된다. 동료 검토는 완벽하지 않으며, LLM의 오류 스타일을 잡아내도록 조정되지 않았을 수 있다.
이에 대한 해결책이 있는데, 결과를 형식화하여 기계 검증을 받는 것이다. 그리고 LLM과 함께라면, 이것이 앞으로 모범 사례가 될 것이라고 감히 말한다.
- drivebyhooting
별로 빠르지 않다.
복잡도 F(n)인 임의의 k-컬러링 알고리즘은 N에 대해 이분 탐색을 수행함으로써 복잡도 lg(N)F(N)인 채색수 알고리즘을 만드는 데 사용될 수 있다.