But how much of the software industry is truly solving inherently complex problems?

At a very conservative guess I'd say no more than 10% (and my actual guess would be <1%)