About: Decision tree model

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Decision tree model Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of queries or tests that are done adaptively, so the outcome of the previous tests can influence the test is performed next. Decision trees models are instrumental in establishing lower bounds for complexity theory for certain classes of computational problems and algorithms. Several variants of decision tree models have been introduced, depending on the computational model and type of query algorithms are allowed to perform.

Attributes	Values
rdfs:label	Decision tree model (en)
rdfs:comment	In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of queries or tests that are done adaptively, so the outcome of the previous tests can influence the test is performed next. Decision trees models are instrumental in establishing lower bounds for complexity theory for certain classes of computational problems and algorithms. Several variants of decision tree models have been introduced, depending on the computational model and type of query algorithms are allowed to perform. (en)
sameAs	Decision tree model Decision tree model
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Reflist dbt:Rp dbt:Short_description dbt:Use_American_English
Subject	Computational complexity theory Decision trees Models of computation
Link from a Wikipage to an external page	http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf%7Cdoi-access=free
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Decision_tree_model?oldid=1068655561&ns=0
Wikipage page ID	22684368 (xsd:integer)
page length (characters) of wiki page	25066 (xsd:nonNegativeInteger)
Wikipage revision ID	1068655561 (xsd:integer)
Link from a Wikipage to another Wikipage	Noam Nisan Nondeterministic algorithm Aanderaa–Karp–Rosenberg conjecture Analysis of Boolean functions Boolean function Monte Carlo algorithm Upper and lower bounds Computational complexity theory Decision trees Models of computation Certificate (complexity) Decision tree Comparison sort Algorithmic complexity Computational geometry Computational model Minimum spanning tree Order statistic Partial function Emory University Permutation Deutsch–Jozsa algorithm Fiber (mathematics) Hao Huang (mathematician) Heapsort Information theory Model of computation Vector space Merge algorithm Las Vegas algorithm
has abstract	In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of queries or tests that are done adaptively, so the outcome of the previous tests can influence the test is performed next. Typically, these tests have a small number of outcomes (such as a yes-no question) and can be performed quickly (say, with unit computational cost), so the worst-case time complexity of an algorithm in the decision tree model corresponds to the depth of the corresponding decision tree. This notion of computational complexity of a problem or an algorithm in the decision tree model is called its decision tree complexity or query complexity. Decision trees models are instrumental in establishing lower bounds for complexity theory for certain classes of computational problems and algorithms. Several variants of decision tree models have been introduced, depending on the computational model and type of query algorithms are allowed to perform. For example, a decision tree argument is used to show that a comparison sort of items must take comparisons. For comparison sorts, a query is a comparison of two items , with two outcomes (assuming no items are equal): either or . Comparison sorts can be expressed as a decision tree in this model, since such sorting algorithms only perform these types of queries. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Decision_tree_model
is rdfs:seeAlso of	Minimum spanning tree
is Wikipage redirect of	Sensitivity Conjecture Sensitivity conjecture Quantum query complexity Algebraic decision tree Linear decision tree Decision tree (model) Decision tree complexity Query complexity
is Link from a Wikipage to another Wikipage of	List of unsolved problems in mathematics Non-constructive algorithm existence proofs 3SUM Aanderaa–Karp–Rosenberg conjecture Andris Ambainis Bentley–Ottmann algorithm Boolean function Centre for Quantum Technologies Certificate (complexity) Decision tree Clique problem Closest pair of points problem Communication complexity Comparison sort Algorithmic complexity Convex hull algorithms Convex polytope List of conjectures Element distinctness problem ID3 algorithm Grover's algorithm Hao Huang (mathematician) Harry Buhrman Euclidean minimum spanning tree Evasive Boolean function Algebraic decision tree Linear decision tree Decision tree (model) Decision tree complexity
is known for of	Harry Buhrman
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Decision_tree_model

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software