은하 알고리즘

은하 알고리즘은 충분히 큰 문제에 대해서는 다른 알고리즘을 능가하는 알고리즘이지만, 실제로는 알고리즘이 결코 사용되지 않을 정도로 "충분히 큰" 알고리즘이다.은하 알고리즘은 리처드 립톤과 켄 리건에 의해 그렇게 이름지어졌다.^[1] 왜냐하면 그것들은 우리가 여기 지구에서 찾을 수 있는 어떤 단순한 지상 데이터 세트에도 사용되지 않을 것이기 때문이다.

사용 사례

이러한 알고리즘이 실제로 사용되지 않더라도 은하 알고리즘은 여전히 컴퓨터 과학에 기여할 수 있다.

• 알고리즘은 비실용적이더라도 결국 실제 알고리즘을 만드는 데 사용될 수 있는 새로운 기법을 보여줄 수 있다.
• 컴퓨터 크기는 교차점까지 따라갈 수 있기 때문에 이전에 비실용적인 알고리즘이 실용화된다.
• 비실용 알고리즘은 여전히 추측한 한계가 달성될 수 있거나 제안된 한계가 잘못되었다는 것을 증명할 수 있으며, 따라서 알고리즘 이론을 진전시킬 수 있다.립톤은 다음과 같이 말한다.^[1]

  이것만으로도 중요할 수 있고 종종 그러한 알고리즘을 찾는 훌륭한 이유가 된다.예를 들어, 만약 내일 거대하지만 가능한 다항식 시간의 구속을 가진 인수 알고리즘이 있다는 것을 보여준 발견이 있다면, 그것은 인수인계에 대한 우리의 믿음을 바꿀 것이다.이 알고리즘은 결코 사용되지 않을 수도 있지만, 앞으로의 연구를 확실히 팩토링으로 구체화시킬 것이다.

  마찬가지로, 부울 만족도 문제에 $대한{\displaystyle }$ O${\displaystyle }$(${\displaystyle n{}^{}}$ 2 $){\$ O${{\bigl (}n^{2^{100}}{\bigr )}}$ 알고리즘은$$ 실제로는 사용할 수 없지만, 컴퓨터 과학에서 가장 중요한 개방적 문제 및 밀레니엄상 문제 중 하나로 간주되는 P 대 NP 문제를 해결할 것이다.^[2]

예

정수 곱하기

은하 알고리즘의 예는 1729차원 푸리에 변환에 기초하여 두 숫자를 곱하는 것으로 알려진 가장 빠른 방법이다.^[3][4]이는 숫자들이 알려진 우주의¹⁷²⁹¹² 원자 수보다 훨씬 큰 최소 2비트(최소 10자리¹⁰³⁸)를 가질 때까지 명시된 효율에 도달하지 못한다는 것을 의미한다.그래서 이 알고리즘은 결코 실제로 사용되지 않는다.^[5]

행렬 곱하기

짐승-강력 곱셈에 대한 첫 번째 개선인 $O{\displaystyle ({n\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$${\displaystyle {\mathrm{)}}^{}}$ ${\displaystyle O(n^{3})$는 $O{\displaystyle }$(n 2.807) ${\displaystyle O(n^{2.$807$})$인 재귀 $알고리즘$인 Strassen 알고리즘이다$.$이 알고리즘은 은하계가 아니며 실제로 사용된다.정교한 그룹 이론을 사용하여 이것의 추가 확장은 Coppersmith-Winograd 알고리즘과 약간 더 나은 후계자들로, $O{\displaystyle }$(${\displaystyle {}^{}}$ $){\displaystyle$O$(n^{2.373})$를 전달한다$.$이는 은하계적 – "우리는 그럼에도 불구하고 빠른 매트릭스 곱셈의 복잡성에 수반되는 거대한 상수들이 대개 이러한 알고리즘을 비실용적으로 만들기 때문에 그러한 개선은 이론적인 관심사일 뿐이라는 것을 강조한다."^[6]

통신 채널 용량

클로드 섀넌은 통신 채널의 용량에 도달할 수 있는 간단하지만 비실용적인 코드를 보여주었다.가능한 모든 $n{\displaystyle }$ ${\displaystyle n}$ -bit$$ 메시지에 임의 코드 단어를 할당하고 가장 가까운 코드 단어를 찾아 디코딩해야 한다.$n{\displaystyle }$ ${\displaystyle n}$을(를) 충분히 크게 선택하면 기존 코드를 모두 능가하고 채널 용량에 임의로 근접할 수 있다.불행히도, 기존 코드를 능가할 만큼 큰$$ $n{\displaystyle }$ ${\displaystyle n}$도 완전히 비현실적이다.^[7]이러한 코드들은 결코 사용되지 않았지만, 오늘날 채널 용량에 임의로 가까운 비율을 달성할 수 있는 보다 실용적인 알고리즘에 대한 수십 년의 연구를 고무시켰다.^[8]

서브그래프

그래프 $G{\displaystyle }$ ${\$$displaystyle G}$에 $H{\displaystyle }$ {\$displaystyle H}$이(가) 마이너로서 포함되어$$ 있는지 여부를 결정하는 문제는 일반적으로 NP-완전하지만, $H{\displaystyle }$ ${\displaystyle H}$이(가$$) 고정되어 있는 경우에는 다항 시간 내에 해결할 수 있다.실험을 위한 영사 시간 여부 H{H\displaystyle}은 미성년자의 G{G\displaystyle}에 이 사건은 O(n2){O(n^{2})\displaystyle},[9]이 n{n\displaystyle}은 수 vertices에 G{G\displaystyle}과 큰 O표기법 숨기는 끊임 없는 말이 맞을 수가 있superexponentially에 H{년.dIsplaystyle H}. 그 상수 2↑↑(2↑↑(2↑↑(h/2)보다)vertices의 H에서 h{h\displaystyle}은 번호{H\displaystyle}h의 경우 .[10]cm부터 4{\displaystyle h=4}크누스의 up-arrow 표기법에서){2\uparrow \uparrow(2\uparrow \uparrow(2\uparrow \uparrow(h/2))\displaystyle)}더 크다. 수 있상수가 ${\displaystyle \genfrac{}{}{0ex}{}{}{}\genfrac{}{}{0ex}{}{\underset{}{{\mathrm{}}^{}}}{}}$ = ${\displaystyle \genfrac{}{}{0ex}{}{\underset{}{{65536인{\mathrm{}}^{}}^{}}}{}}$ 2 ${\displaystyle \genfrac{}{}{0ex}{}{\underset{}{{{\cdot {}^{}}^{}}^{}}}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{\underset{}{{{{{2\mathrm{}}^{}}^{}}^{}}^{}}}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{\underset{}{{{{{}^{}}^{}}^{}}^{}}}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{n}{}}$ ${\displaystyle {\atop{\}{{\\brace{2^{2^{\cdot^{\cdot ^{$2}}}}} \at n}}을$$(를) 가진 $\ot$n}}}}}}}}}}을(를) 초과하므로 합리적으로 계산할 수 없다.For ${\displaystyle h=6}$, the constant is far larger: ${\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (6/2)))=2\uparrow \uparrow {\Bigl (}2^{\cdot ^{\cdot ^{2}}}{\Bigr )}}$, where the part ${\displaystyle$$2^{\cdot ^{\cdot ^{2}}}$는 2의 16개의 지수 스택으로, 정확한 값을 실질적으로$$ 계산할 수 없을 정도로 큰 숫자다.^[11]전체 표현은 그 많은 2매의 파워타워다.

암호 해독

암호학자의 경우 암호 "차단"은 흉포력 공격보다 더 빠른 것으로, 즉 가능한 각 키에 대해 한 번의 시험 암호 해독을 수행하는 것이다.많은 경우에서, 그것들이 가장 잘 알려진 방법임에도 불구하고, 그것들은 여전히 현재의 기술로는 실현이 불가능하다.한 예로 128비트 AES에 대해 알려진 최고의 공격이 있는데, ${\displaystyle {126}^{}}$ ${\$ 2$^{126}$ 조작만$$ 하면 $된다{\displaystyle {\mathrm{}}^{}}$.^[12]실용적이지 않음에도 불구하고 이론적 단절은 때때로 취약성 패턴에 대한 통찰력을 제공할 수 있다.

출장 판매원 문제

수십 년 동안, 미터법 공간에서 여행하는 세일즈맨 문제에 대해 가장 잘 알려진 근사치는 최적보다 최대 50% 더 긴 경로를 생성하는 매우 단순한 크리스토피데스 알고리즘이었다.(다른 많은 알고리즘은 대개 훨씬 더 잘 할 수 있지만, 그럴 가능성은 없다.)2020년에는 ${\displaystyle {10}^{}}$- ${\displaystyle {34}^{}}$ ${\$까지 이를 이길 수 있는 훨씬 더 새롭고 복잡한 알고리즘이 발견되었다.^[13]비록 아무도 이 알고리즘의 아주 사소한 최악의 경우 개선을 위해 이 알고리즘으로 전환하지는 않을 것이지만, 그것은 여전히 중요한 것으로 여겨진다. "이 작은 개선은 이론적인 문제점과 심리적인 문제 모두를 뚫고 지나가기 때문이다."^[14]

후터 검색

"Hutter search"라는 단일 알고리즘은 몇 가지 주의사항을 배제하고 점증적으로 최적의 시간에 잘 정의된 문제를 해결할 수 있다.가능한 모든 알고리즘(실시간 기준)을 검색하는 동시에 가능한 모든 증명(증거 길이 기준)을 검색해 각 알고리즘에 대한 정확성 증명을 찾는 방식으로 작동한다.정확성 증명은 크기가 유한하기 때문에 "만일"은 상수를 추가하며 점증적 런타임에는 영향을 주지 않는다.그러나 이 상수는 너무 커서 알고리즘은 완전히 비실용적이다.^[15][16]예를 들어, 주어진 알고리즘의 정확성에 대한 가장 짧은 증거가 1000비트 길이라면, 검색은 먼저 다른 최소 2개의⁹⁹⁹ 잠재적 증거를 검사할 것이다.

최적화

로그 냉각 일정과 함께 사용할 경우 시뮬레이션된 어닐링은 최적화 문제의 전지구적 최적화를 찾는 것으로 입증되었다.그러나 이러한 냉각 스케줄은 완전히 비실용적인 가동 시간을 초래하며, 결코 사용되지 않는다.^[17]그러나 이러한 이상적인 알고리즘이 존재한다는 것을 알게 되면서 복잡한 최적화 문제에 대해 매우 우수한(최적성은 아니지만) 솔루션을 찾을 수 있는 실용적인 변형이 생겨났다.^[18]

참조