A computation tree is a representation for the computation steps of a non-deterministic Turing machine on a specified input. A computation tree is a rooted tree 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 output nodes of the tree are called leaves.
In a computation tree each output node is labeled Yes or No. If a tree, T, with an input space X, if 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 computation time for the Turing machine on that input.
One of the primary methods of showing that a computational problem L is complete for a given complexity class C is to show that the computation tree of any algorithm in C can be directly analyzed in terms of L.
Famous quotes containing the words computation and/or tree:
“I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...”
—Minnie Maddern Fiske (1865–1932)
“A tree is beautiful, but what’s more, it has a right to life; like water, the sun and the stars, it is essential. Life on earth is inconceivable without trees. Forests create climate, climate influences peoples’ character, and so on and so forth. There can be neither civilization nor happiness if forests crash down under the axe, if the climate is harsh and severe, if people are also harsh and severe.... What a terrible future!”
—Anton Pavlovich Chekhov (1860–1904)