계산 트리

계산 트리는 특정 입력에 비결정론적 튜링 기계의 계산 단계를 나타내는 것이다.^[1]계산 트리는 노드와 가장자리의 뿌리가 있는 나무다.트리의 각 노드는 단일 계산 상태를 나타내는 반면, 각 에지는 가능한 다음 계산으로의 전환을 나타낸다.트리의 노드 수는 트리의 크기, 루트에서 주어진 노드까지의 경로의 길이는 노드의 깊이다.출력 노드의 가장 큰 깊이는 트리의 깊이다.나무의 잎을 출력 노드라고 한다.

결정 문제에 대한 계산 트리에서 각 출력 노드는 예 또는 아니오로 레이블이 지정된다.$입력{\displaystyle }$ 공간이 X인 트리 T가 x ${\displaystyle \in }$ ${\displaystyle X}$ ${\displaystyle x\in$ X$}$이고 x 경로가$$ yes로 표시된 노드에서 끝나는 경우 입력 X가 허용된다.그렇지 않으면 거부된다.^[2]

주어진 입력에 대한 계산 트리의 깊이는 해당 입력에 대한 튜링 기계의 계산 시간이다.^[1]

계산 트리는 또한 계산 기하학 및 실제 수 계산에서 문제의 계산 복잡성을 연구하기 위해 사용되었다.^[3][4]

참조