computational complexity theory noun1 •A theory focusing on classifying computational problems according to their resource usage, and relating these classes to each other. formscomputational complexity theories