Talk:Decision tree model

Merger proposal

I think it might be good to merge Decision tree model and Decision tree complexity, since there's overlapping information and they can be treated together in one article. --Robin (talk) 04:25, 7 December 2009 (UTC)

Support. I would say, they have complementary, rather than overlapping information, but the subject is definitely overlapping, so the merge is fairly straightforward cut'and-paste, and I am going ahead, since no objection voiced so far. Also, from the contents of both pages (namely, section titles) I see that the common title would be "DT model," rather than "DT complexity". Twri (talk) 17:29, 30 December 2009 (UTC)

Certificate complexity (nondeterministic decision tree complexity)

I have added a section on certificate complexity. However, I have not yet added the relationships to the other complexity measures. Feel free to add this! —Preceding unsigned comment added by 129.97.9.222 (talk) 19:46, 19 May 2010 (UTC)

The "Simple Decision Tree" bound for minimum selection is slack, and consequently a bad example.

Unless I'm majorly misunderstanding something, n - 1 comparisons are clearly needed. I edited to reflect this. I would have also linked to the "Tournament selection" section of Selection algorithm, since that algorithm solves the problem with n - 1 comparisons, but I don't know how to link to a section. A tournament selection page does exist, but unfortunately it talks about a particular application of tournament selection (to genetic algorithms), and I don't want to rock the boat too much.

Multiple issues/suggestions

(Some of these suggestions may not be appropriate for a general Wikipedia audience. But then again, I'm not sure the series of inequalities at the end of the article is appropriate for a general Wikipedia audience, either.)

• The first "classification" section should be by query type, not by "query computational complexity". First, for purposes of proving lower bounds, time is defined to be the depth of the tree in this model, so each query takes constant "time" _by definition_. But more importantly, there is a significant difference in the expressiveness and complexity of boolean decision trees, comparison trees, and 4-linear decision trees, each of which use constant-CPU-time queries.

• Decision trees do not compute functions only from {0,1}^n to {0,1}. For example, a comparison tree for sorting $n$ items from the totally-ordered domain D is a function from D^n to the permutation group S_n. Similarly, an algebraic decision tree for 3SUM is a function from ℝ^n (or perhaps ℤ^n) to {0,1} (or more precisely, to the booleans {true, false}).

• There should be a separate preliminary section on information-theoretic lower bounds like Ω(n log n) for sorting and Ω(log n) for searching/selection/minimum, which don't depend at all on the type of decision tree, and which hold even in the average case and therefore, by Yao's principle, for randomized decision trees.

• "Simple decision trees" should really be called "comparison trees". This section should retain the easy Ω(n) lower bound argument for minimum-selection, and maybe add the easy adversary argument that implies Ω(n log n) lower bound for element uniqueness. (If you don't know their order, you don't know that all elements are unique.)

• The section on linear decision trees should have some more concrete examples, like Dobkin and Lipton's Ω(n log n) lower bound for element uniqueness, or their Ω(n^2) lower bound for knapsack, via convexity arguments (and perhaps the symmetric polynomial upper bounds for knapsack by Meiser and Meyer auf der Heide).

• There should be another separate section on boolean decision trees (aka "(bit-)query complexity"), eventually connecting to evasiveness and the [Aanderaa-Rosenberg conjecture], and to the later discussion of deterministic/randomized/quantum query complexity.

• Finally, there should be at least a token discussion of (non-)uniformity. For example, Fredman described a non-uniform family of O(n^2)-depth linear decision trees for X Y sorting, but the fastest known uniform algorithm runs in O(n^2 log n) time. (See also Grønlund and Pettie's recent results for 3SUM, which use Fredman's trick.) Similarly, Meyer auf der Heide described a non-uniform family of linear decision trees for the knapsack problem, but we still believe P≠NP.

— Jeff Erickson (talk) 19:42, 27 June 2019 (UTC)

I believe I have addressed all of the points here except for the discussion of the Aanderaa-Rosenberg conjecture and non-uniformity. Fawly (talk) 07:30, 25 November 2020 (UTC)

Boolean function complexity section

I made edits with the intention of finding a place here for a section on the sensitivity conjecture, which was previously out-of-place in triangle-free graph. In the process, I may have made this page a bit of a WP:COATRACK, so perhaps the portion of this article on Boolean function complexity measures should be re-split into its own article. I don't have a strong opinion on how to proceed, though. Fawly (talk) 07:27, 25 November 2020 (UTC)