> NP-completeness theory, however, does not explain or predict the unreasonable effectiveness of SAT solvers.

I don't think that's a fair characterisation. Clearly, the SAT subset that SAT solvers solve efficiently is in P, so in that sense complexity theory "explains" it and even "predicts" it: clearly, there are subsets of SAT in P; some simple ones, such as 2SAT, can be easily described.

What complexity theory is yet to do is:

1. Either prove that the subset of SAT that can be solved efficiently covers all of SAT (in which case either P=NP or NP can be solved with such a low exponent that makes it tractable in practice) or identify and succinctly describe the subset of SAT that modern solvers solve efficiently, and it is in that sense that it doesn't yet "predict" it. But there are many open questions (including P vs NP) in complexity theory; that doesn't mean that the discipline is flawed. Many problems studied in complexity theory originate from practical questions, such as cryptography, and complexity theory does successfully and usefully explain and predict such real-world "phenomena".

2. Explain why that subset of SAT is prevalent in practice (making solvers "effective"). I'm not sure this is the job for complexity theory or any theoretical discipline for that matter (as opposed to empirical ones); after all theoretical computer science is meant to be theoretical. But there are mathematical disciplines (e.g. random graph theory) that do describe and even explain and predict mathematical structures that are more likely to arise in "nature".

> U.S. TCS has a quite narrower scope than European TCS, which I find unfortunate.

TCS is generally considered to have two primary subdisciplines: Theory of Computation (ToC, sometimes also referred to as "Theory A"), which is concerned with complexity and algorithms, and Theory of Programming (ToP, sometimes also referred to as "Theory B"), which is concerned with programming languages and type systems (and may be considered a sub-discipline of formal logic). Indeed, US ToC is more prominent in the US while ToP is more prominent in Europe, but I don't think some of the other CS sub-disciplines Moshe mentions (such as databases) are commonly considered theoretical computer science.

I don't have a position on the utility of describing theoretical computer science as a branch of mathematics or not doing so, but the very name "theoretical computer science" acknowledges that there are other sub-disciplines in computer science that are empirical rather than theoretical (such as studying the mistakes programmers empirically make, or the common causes for cascading failures, or studying side-channel attacks etc. etc.).

I don't think that those who consider TCS to be a branch of mathematics also consider all of CS to be a branch of mathematics or claim that theoretical computer science should aim to answer all interesting questions in computing, just as theoretical physics acknowledges the necessity of experimental physics and doesn't claim to cover everything physicists do.

As in theoretical physics and mathematics, results in theoretical computer science do sometimes explain and predict things we observe in the real world and sometimes not yet. But in all these cases, the theoretical subdisciplines aren't wholly subservient to the empirical ones or vice-versa.

As an example, the question of computability (decidability) isn't directly practical (as many decidable problems arent practically tractable), but the more practical question of tractability/complexity directly evolved from the study of computability.