D(f) vs ndegε(f)2 · ndegε(¬f)2

Computational verification of the conjecture that decision-tree complexity is bounded by the product of squared approximate nondeterministic degrees.

100%
Conjecture Verified
0.85
Max Ratio
0.23
Mean Ratio
1.6x
Tightening Factor

Results by Function Family (epsilon = 0.1)

FamilyCountMean RatioMax Ratio
AND/OR120.140.31
Threshold180.280.67
Address80.350.72
Tribes60.220.48
Parity40.080.12
Recursive Maj.60.410.85

Ratio by Function Family

Epsilon Sensitivity

Scaling with n

Partial vs Conjectured Bound