I feel like you may be ignoring special functions, although you did mention NP completeness. The un-mathematized areas of CS make liberal use of intuitive formulations of feedback systems, and are more or less unassailable to analysis. Computer Engineering can tackle some of these, but there is a lot of pressure to swap these intuitively good solutions to worse, but more tractable ones.

CS can and has the taken head-on a large number of problems mathematics cannot handle. These are hard to sciencify, which is why the prominent direction of CS seems to instead be expressiveness. You can't take engineering out of computing, and CS seems to be yet another attempt at systems study.