Дерево вычислений - Computation tree
Вычисление дерево является представлением шагов вычисления недетерминистических машин Тьюринга на заданный входе. Дерево вычислений - это корневое дерево узлов и ребер. Каждый узел в дереве представляет отдельное вычислительное состояние, а каждое ребро представляет переход к следующему возможному вычислению. Количество узлов дерева - это размер дерева, а длина пути от корня до данного узла - это глубина узла. Наибольшая глубина выходного узла - это глубина дерева. Листья дерева называются выходными узлами.
В дереве вычислений для задачи решения каждый выходной узел помечен как «Да» или «Нет». Если дерево T с входным пространством X, если и путь для x заканчивается в узле, помеченном как «Да», то вход x принимается. В противном случае он отклоняется.
Глубина дерева вычислений для данного входа - это время вычисления машины Тьюринга на этом входе.
Деревья вычислений также использовались для изучения вычислительной сложности задач вычислительной геометрии и вычислений действительных чисел .