다음 계산 문제 (또는 관련 결정 문제)를 고려하십시오. 이진수로 인코딩 된 두 개의 양의 정수가 주어지면 최대 공약수 (gcd)를 계산하십시오. 이 문제에 포함 된 가장 복잡한 클래스는 무엇입니까? 당신은 참조를 제공 할 수 있습니까?
이 질문에서 나는 주로 실행 시간에 점근선 경계에 관심이 없지만 복잡한 클래스에 관심이 있습니다. AC에 문제가 있습니까? AC0에 속하지 않는 것으로 입증 될 수 있습니까? P와 관련된 다른 복잡성 클래스는 무엇입니까?
답변
이것은 복잡성 이론에서 가장 중요한 문제입니다. NC에서 GCD를 계산할 수 있는지, GCD를 계산하는 것이 P- 완전인지는 알 수 없습니다. 최고의 병렬 알고리즘은 하위 선형 병렬 실행 시간을 가지며, 이러한 알고리즘 중 하나는 Sorenson 때문입니다.
소렌슨 두 개의 빠른 GCD 알고리즘 . 알고리즘 저널, 1994.
내가 실수하지 않으면 NC에서 두 정수가 상대적으로 소수인지 여부를 결정할 수 있는지조차 알 수 없습니다.