On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs.

Stasys Jukna Alexander A. Razborov Petr Savický Ingo Wegener

Published in: MFCS (1997)

Keyphrases

decision trees
np hard
computational complexity
np complete
training data
search algorithm
decision tree induction
boosted decision trees