The Aanderaa–Karp–Rosenberg conjecture also states that the randomized decision tree complexity of non-trivial monotone functions is Θ(n2).
Conjectura Aanderaa–Karp–Rosenberg prevede și că complexitatea arborelui de decizie randomizat a funcțiilor monotone netriviale este Θ(n2).