ABSTRACT
Concrete complexity theory is the study of what idealized computers can or cannot do, subject to relevant limitations of resources, in the context of specific problems of special interest. The results are cast in terms of the same models used in abstract complexity, but when positive results are obtained, the algorithms are often reassessed and modified to run efficiently on actual computers. Concrete complexity is an entirely open-ended area touching virtually every area of mathematics. Essentially every area of mathematics is being restudied from the computational complexity point. Methods in mathematics for decomposing semigroups lead to the decomposition of these automata into irreducible component machines from which all machines are built. Automatic theorem proving in the sense of automatically developing proofs of interesting mathematical conjectures is a ridiculously over-ambitious goal that is commonly rejected. However, the more modest goal of using automated deduction in conjunction with mathematicians is being pursued.
