Constructing optimal binary decision trees is NP-complete
The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“The efficiency in reaching the exit of a maze dramatically decreases with the number of sites in the structure, rapidly making this problem intractable1.”
From Fast escape of a quantum walker from an integrated photonic maze (2016) · cites this paper as [1]
Citations
Cites
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Optimal Binary Identification Procedures
Garey, M. R. (1972) · SIAM Journal on Applied Mathematics · doi:10.1137/0123019 · Cited by 154
Conversion of limited-entry decision tables to computer programs
Pollack, S. L. (1965) · Communications of the ACM · doi:10.1145/365660.365681 · Cited by 61
Combining decision rules in a decision table
Shwayder, K. R. (1975) · Communications of the ACM · doi:10.1145/360933.360997 · Cited by 22
Algorithm 268: ALGOL 60 reference language editor [R2]
McKeeman, W. M. (1965) · Communications of the ACM · doi:10.1145/365660.365673 · Cited by 9
Cited by
Classification and Regression Trees.
Gordon, A. D., Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984) · Biometrics · doi:10.2307/2530946 · Cited by 23,522
Arrieta, A. B., Díaz-Rodríguez, N., Del Ser, J., Bennetot, A., Tabik, S., Barbado, A., García, S., Gil-López, S., Molina, D., Benjamins, R., et al. (2019) · arXiv · doi:10.48550/arxiv.1910.10045 · Cited by 11,321
“Decision trees are hierarchical structures for decision making used to support regression and classi-fication problems [132,180] .”
Barredo Arrieta, A., Díaz-Rodríguez, N., Del Ser, J., Bennetot, A., Tabik, S., Barbado, A., Garcia, S., Gil-Lopez, S., Molina, D., Benjamins, R., et al. (2020) · Information Fusion · doi:10.1016/j.inffus.2019.12.012 · Cited by 10,423
“Decision trees are hierarchical structures for decision making used to support regression and classi-fication problems [132,180] .”
Wrappers for feature subset selection
Kohavi, R., & John, G. H. (1997) · Artificial Intelligence · doi:10.1016/s0004-3702(97)00043-x · Cited by 8,947
Ensemble methods in machine learning
Dietterich, T. G. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45014-9_1 · Cited by 8,408
Metadata
- Authors
- Hyafil, L., & Rivest, R. L.
- Affiliations
- Institut national de recherche en sciences et technologies du numérique (FR)
- Massachusetts Institute of Technology (US)
- ORCID
- Rivest, Ronald L.
- Venue
- Information Processing Letters
- Publisher
- Elsevier BV
- Published
- 1976-05
- Volume
- 5
- Issue
- 1
- Pages
- 15-17
- ISSN
- 0020-0190 (ISSN-L)
- OpenAlex
- W1970074386
- Cited by
- 959
- References
- 7
- Citations by year
- 2026: 21 · 2025: 26 · 2024: 36 · 2023: 44 · 2022: 58 · 2021: 60 · 2020: 48 · 2019: 35 · 2018: 38 · 2017: 39 · 2016: 40 · 2015: 23 · 2014: 36 · 2013: 39 · 2012: 29
- FWCI
- 1.60
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.elsevier.com/tdm/userlicense/1.0/ (tdm)
- Locations
- Information Processing Letters (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Information Systems › Data Mining Algorithms and Applications
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- binary decision tree, NP-completeness, column generation, multi-class classification, cutting planes, discrete optimization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Constructing optimal binary decision trees is NP-complete. https://app.cochat.ai/papers/10.1016/0020-0190(76)90095-8
- The paper
- Hyafil, L., & Rivest, R. L. (1976). Constructing optimal binary decision trees is NP-complete. Information Processing Letters. https://doi.org/10.1016/0020-0190(76)90095-8
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.