Reproduce “A Local Approach to Studying the Time and Space Complexity of Deterministic and Nondeterministic Decision Trees” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Kerven Durdymyradov, Mikhail Moshkov
Durdymyradov and Moshkov characterize the time and space complexity of deterministic and nondeterministic decision trees operating under a local attribute constraint for infinite binary information systems, classifying such systems into three distinct categories based on their complexity growth patterns and identifying different time-space trade-offs.
Key insights
- Two properties of information systems—the condition of reduction and the independence dimension—are sufficient to characterize the asymptotic growth of all four complexity measures.
- For space complexity in the local approach, nondeterministic decision trees offer no asymptotic advantage over deterministic ones ($L_{la}^U(n) = L_{ld}^U(n)$).
- While deterministic trees are always "ld-reachable" (simultaneously optimal in time and space), nondeterministic trees in one class ($W_l^1$) exhibit a time-space trade-off.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.