문제 해결에 대한 체계적인 접근 방식으로 알려진 분야인 컴퓨터 과학의 초창기부터 무작위성은 중요한 역할을 해왔습니다. 세계 최초의 범용 전자 컴퓨터에서 실행되는 최초의 프로그램은 핵 과정을 시뮬레이션하기 위해 무작위성을 사용했습니다. 그 이후로 천체 물리학, 기후 과학 및 경제학에서 유사한 접근 방식이 사용되었습니다. 이 모든 경우에 연결 난수 알고리즘의 특정 단계에서 연구원은 복잡한 프로세스가 발생할 수 있는 여러 가지 방식에 대한 불확실성을 설명하는 데 도움이 됩니다.

그러나 알고리즘에 임의성을 추가하면 명확한 참 또는 거짓 질문에 대한 정답을 계산하는 데 도움이 될 수 있습니다. "그냥 '좋아, 포기할게, 시도하지 않을게, 그냥 아무거나 골라보자'라고 말하면 된다"고 말했다. 에릭 블레이스, 워털루 대학의 컴퓨터 과학자. "너무 많은 문제에 대해 성공적인 접근 방식이 됩니다."

주어진 숫자가 소수(1과 자기 자신으로만 나눌 수 있음)인지 합성수(다른 정수로도 나눌 수 있음)인지 확인하고 싶다고 가정해 보겠습니다. 가능한 모든 인수로 나누려고 할 수 있지만 많은 수의 경우 이 "무차별 대입(brute force)" 방법과 기타 인수분해 알고리즘은 극도로 느립니다. 그리고 숫자가 합성수로 판명되면 인수분해 알고리즘이 약수의 값을 알려줍니다. 요청한 것보다 더 많은 정보입니다. 숫자의 "primality"에만 관심이 있다면 더 효율적인 알고리즘이 있습니까?

임의성을 사용하는 경우가 있습니다. 기본 아이디어는 17세기 프랑스 수학자 피에르 드 페르마(Pierre de Fermat)의 "작은 정리.” Fermat는 두 개의 정수를 고려했습니다. N 과 x. 그는 만약 N 는 소수이고, 그러면 x^N - x 항상 의 배수입니다 N, 값에 관계없이 x. 동등하게, 만약 x^N - x 의 배수가 아닙니다 N다음, N 소수가 될 수 없습니다. 그러나 그 반대의 진술이 항상 참인 것은 아닙니다. x^N - x 의 배수입니다 N다음, N 일반적으로 소수이지만 항상 소수는 아닙니다.

페르마의 작은 정리를 소수 검정으로 바꾸려면 다음을 취하십시오. N 당신이 관심있는, 선택 x 무작위로 두 숫자를 대입 x^N - x. 결과가 배수가 아닌 경우 N, 그러면 완료됩니다. 알다시피 N 확실히 합성이다. 결과가 배수인 경우 N다음, N 아마도 프라임 일 것입니다. 이제 다른 무작위 선택 x 다시 시도하십시오. 대부분의 경우 수십 번 시도한 후에 거의 확실하게 결론을 내릴 수 있습니다. N 소수입니다. Blais는 "이 작업을 적은 횟수만 수행하면 오류가 발생할 확률이 지금부터 답을 볼 때까지 소행성이 지구에 충돌할 확률보다 적습니다."라고 말했습니다.

처음으로 소수 테스트 (Fermat의 작은 정리에 대한 개선에 기반한) 무작위 알고리즘을 사용하여 새로운 시대를 열었습니다. 문제 이후의 문제는 비무작위 또는 결정론적 알고리즘을 사용하는 것보다 무작위로 해결하기가 훨씬 쉬운 것으로 판명되었습니다. 핵심은 각 문제를 일부 숫자에 대한 적절한 값이 주어졌을 때 신속하게 해결할 수 있는 문제로 재구성하는 것이었습니다. x, 그런 다음 거의 모든 x 할것이다. 이 솔루션은 연구원들이 특정 선택이 좋은지 여부를 결정하는 방법을 알지 못하더라도 작동합니다. 수학자들은 이 특이한 도전이 건초 더미에서 건초 찾기.

그러나 이러한 성공으로 연구자들은 왜 무작위성이 무작위가 아닌 숨겨진 패턴을 찾는 것과 관련된 소수성 테스트와 같은 문제에 도움이 되는지 궁금해했습니다. "약간 역설적인 부분이 있습니다." 라훌 산타남, 옥스퍼드 대학의 컴퓨터 과학자. "순수한 무작위성은 문제를 해결하는 구조를 파악하는 데 도움이 됩니다."

1994년에 컴퓨터 과학자 Noam Nisan과 아비 위그더슨 무작위성은 유용하지만 필요하지 않을 수 있음을 보여줌으로써 이러한 혼란을 해결하는 데 도움이 되었습니다. 그들 증명 두 가지 중 하나가 참이어야 합니다. 임의성을 사용하여 효율적으로 해결할 수 있는 모든 문제가 빠른 결정론적 알고리즘을 가지고 있거나, 악명 높게 어려운 많은 문제가 비밀리에 쉽습니다. 컴퓨터 과학자들은 두 번째 가능성이 매우 희박하다고 생각합니다.

실제로 컴퓨터 과학자들은 무작위 버전으로 시작한 다음 "무작위 해제"하여 결정론적 알고리즘을 개발하는 것이 더 쉽다는 것을 종종 알게 됩니다. "일단 가지고 있으면 결정론적으로 만드는 매우 분명한 방법이 갑자기 보입니다."라고 말했습니다. 엘리 우팔, Brown University의 컴퓨터 과학자. "하지만 확률론적 질문으로 무작위 방식으로 생각하지 않았다면 아마 생각하지 않았을 것입니다."

Nisan과 Wigderson의 획기적인 증명이 있은 지 거의 30년이 지난 후에도 무작위 알고리즘은 여전히 ​​인기가 있습니다. 2002년이 되어서야 세 명의 연구원이 원시성 테스트를 무작위화 해제하는 방법을 찾았고 실제로는 그들의 알고리즘 최고의 무작위 알고리즘보다 훨씬 느립니다. 다른 문제의 경우 어디서부터 시작해야 할지조차 알기 어렵습니다. 가장 잘 알려진 알고리즘에는 무작위성을 통해서만 벗어날 수 있는 닭과 달걀 문제가 있습니다.

그래프 이론의 최근 돌파구가 바로 그런 경우입니다. 작년에 XNUMX명의 컴퓨터 과학자들이 빠른 알고리즘 일부 세그먼트가 총 경로 길이에 더해지는 것이 아니라 빼는 경우에도 작동하는 그래프(선 세그먼트로 연결된 노드 웹)를 통해 최단 경로를 찾기 위한 것입니다. 그들의 알고리즘에는 특정 세그먼트를 삭제하고 단순화된 그래프의 문제를 해결한 다음 삭제된 세그먼트를 고려하여 그래프를 더 간단한 것으로 변환하는 작업이 포함되었습니다. 삭제된 세그먼트를 너무 많이 통과하는 최단 경로가 없으면 알고리즘이 빠르게 실행된다는 것을 증명할 수 있습니다. 그렇지 않으면 마지막 단계가 너무 오래 걸립니다.

그러나 먼저 삭제할 세그먼트를 결정하는 방법은 무엇입니까? 결정론적으로 이상적인 세그먼트 세트를 찾는 것은 어려울 뿐만 아니라 불가능합니다. 세트는 가장 짧은 경로, 즉 세 명의 연구원이 해결하려고 했던 바로 그 문제에 따라 다릅니다. 그러나 삭제할 최적의 세그먼트 집합을 찾을 수는 없었지만 대부분의 임의 선택이 꽤 좋으며 자체 참조 루프를 끊기에 충분하다는 것을 증명할 수 있었습니다. 알고리즘이 불행한 선택을 하고 마지막 단계에서 수렁에 빠지는 드문 경우에 그들은 그냥 멈추고 다시 실행할 수 있습니다.

"무작위성은 기본적으로 최적의 솔루션을 모른 채 최적의 솔루션에 대해 어떤 것이 참인지 확인하는 방법입니다."라고 말했습니다. 아론 번스타인, 새로운 알고리즘의 저자 중 한 명.

임의성은 암호화에서 게임 이론, 기계 학습에 이르기까지 컴퓨터 과학에서 수많은 다른 용도를 발견했습니다. 여기에 머물 가능성이 있습니다.