Computation tree

A computation tree is a representation for the computation steps of a <a href="/facts/Non-deterministic_Turing_machine/zv2x6XPG">non-deterministic Turing machine</a> on a specified input. A computation <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> is a <a href="/facts/Rooted_tree/TCWk4Joy">rooted tree</a> of nodes and edges. Each node in the tree represents a single computational state, while each edge represents a transition to the next possible computation. The number of nodes of the tree is the size of the tree and the length of the path from the root to a given node is the depth of the node. The largest depth of an output node is the depth of the tree. The leaves of the tree are called output nodes. 
In a computation tree for a <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a>, each output node is labeled Yes or No. If a tree, T, with an input space X, if 
 
 
 
 x
 ∈
 X
 
 
 {\displaystyle x\in X}
 
 and the path for x ends in node labeled yes, then the input x is accepted. Else it is rejected.
The depth of the computation tree for a given input is the <a href="/facts/Computation_time/77T62gmf">computation time</a> for the Turing machine on that input.
Computation trees have also been used to study the computational complexity of problems in <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a> and <a href="/facts/Real_number/R02gw5Pb">real number</a> calculations.

Computation tree open-in-new

Computation tree