어떤 포셋이 주어졌을 때, 해당 집합이 어디에 있는지를 확인하기 위한 알고리즘을 찾아보자.
Galois Group를 계산하는 알고리즘을 구현하다가 필요하게 되어 생각하게 되었다. 어떤 Theorem에 의하면 어떤 Galois Group가 어떤 그룹에 포함되는지를 확인할 수 있다고 한다. (관계가 반대일 수 있음) 포셋으로 보면 relation(포함관계)을 정의할 수 있는 셈. 주어진 포셋의 원소임을 알고있고, 그에 따른 relation을 확인할 수 있다. 즉 포셋 관계를 계산할 수 있다. 그렇다면, 어떤 원소인지는 모르는 값(Galois Group)을 찾기 위한 방법이 필요했다.
Galois Group을 계산하는게 애초의 목적이다보니 하나의 가정이 있긴 하다. Maximum element가 존재한다는 것이다.
다만 앞의 가정은 복잡도 면에서 크게 중요하다는 생각은 들지 않았다. worst case는 항상 존재할 테니. 포셋의 모든 원소마다 관계가 정의되지 않는다면? 각각 하나씩 확인하는 수밖에 없다. Maximum element가 존재해도 벌어질 수 있는 상황일 거 같다. 일반적으론.
최악의 상황이 나와도 된다고 생각하면 뭘 좀 더 해볼 수 있을까 생각했다. Maximum element가 존재한다면 하나씩 차례대로 확인해서 top to bottom으로 내려갈 수 있을 것이다. Maximum element의 maximal element들과 관계를 확인해서 가능성이 있는 원소와 없는 원소를 빠르게 추릴 수 있다. 예로, A보다 작고, B보다도 작다면, 우리는 A, B모두와 공통되게 작은 원소들로 추릴 수 있다.
사실 포셋 구조가 고정이라 일반적인 포셋 탐색 알고리즘 고민은 잘 모르겠다. 그리고 포셋의 개수 자체가 그렇게 많지 않기도 하고.. Galois Group을 계산하는 과정에 대해서는 새로운 포스트를 통해서 서술하기로 한다.