Time and space complexity of deterministic and nondeterministic decision trees

DOI10.1007/s10472-022-09814-1OpenAlexW4295137004MaRDI QIDQ2679423

Mikhail Ju. Moshkov

Publication date: 20 January 2023

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2201.01013

zbMATH Keywords

time complexitycomplexity classesspace complexitytime-space trade-offdeterministic decision treesnondeterministic decision trees

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Totally optimal decision trees for Boolean functions
• On topological lower bounds for algebraic computation trees
• Combinatorial machine learning. A rough set approach.
• Rudiments of rough sets
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• Partial covers, reducts and decision rules in rough sets. Theory and applications
• Time-space trade-offs for branching programs
• Information systems theoretical foundations
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• On the complexity of computations under varying sets of primitives
• An exponential lower bound on the size of algebraic decision trees for MAX
• Logical analysis of numerical data
• Time-space tradeoffs for branching programs
• Recent advances in the theory and practice of logical analysis of data
• A SAT-based approach to learn explainable decision sets
• Complexity measures and decision tree complexity: a survey.
• Independence number and the complexity of families of sets
• Three approaches to data analysis. Test theory, rough sets and logical analysis of data.
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• One-way functions and the nonisomorphism of NP-complete sets
• Foundations of Rule Learning
• Lower bounds for algebraic decision trees
• Multidimensional Searching Problems
• Decision and Inhibitory Trees and Rules for Decision Tables with Many-valued Decisions
• Data Mining with Decision Trees
• Comparative Analysis of Deterministic and Nondeterministic Decision Tree Complexity Local Approach
• Transactions on Rough Sets III
• Decision tree complexity and Betti numbers
• Optimal classification trees

This page was built for publication: Time and space complexity of deterministic and nondeterministic decision trees