본 논문은 AND-OR 트리 계산에서 제로-에러 랜덤 복잡도(최악의 입력에 대한 최소 비용)를 연구합니다. 알고리즘에 트리 형태에는 제한 없이, 루트의 부울 값을 찾는 것에 대한 다양한 제한을 부과합니다. 특정 대칭 조건을 만족하는 트리의 경우, Saks와 Wigderson (1986)이 제안한 방향 알고리즘이 랜덤 복잡도를 달성하는 것으로 알려져 있습니다. 하지만, 어떤 방향 알고리즘도 랜덤 복잡도를 달성하지 못하는 불균형적인 트리의 예시도 존재합니다 (Vereshchagin 1998). 본 연구는 일반적인 랜덤 부울 의사결정 트리와 특수한 경우인 방향 알고리즘 간의 차이가 발생하는 지점을 밝히고자 합니다. 본 논문은 임의의 AND-OR 트리에 대해, 방향 알고리즘보다 넓은 범주인 랜덤 깊이 우선 탐색 알고리즘이 방향 알고리즘과 동일한 평형을 가짐을 보여줍니다. 따라서 임의의 AND-OR 트리에 대해 성립하는 평형 불평등에 대한 붕괴 결과를 얻습니다. 이는 깊이 우선 탐색 알고리즘조차도 가장 빠르지 못한 경우가 존재함을 의미하며, 평형 불평등에 대한 분리 결과를 이끌어냅니다. 또한, 분리 결과 증명을 위한 핵심 개념으로 새로운 알고리즘을 제시합니다.
