Thanks for the insight.

Many classification algorithms have a polynomial complexity, but not 100% accuracy. So how do we address complexity when dealing with them? Or do we classify something like BPP?