In artificial intelligence (sometimes called machine intelligence or computational intelligence), there are several problems that are based on mathematical topics, especially optimization, statistics, probability theory, calculus and linear algebra.
Marcus Hutter has worked on a mathematical theory for artificial general intelligence, called AIXI, which is based on several mathematical and computation science concepts, such as reinforcement learning, probability theory (e.g. Bayes theorem and related topics) measure theory, algorithmic information theory (e.g. Kolmogorov complexity), optimisation, Solomonoff induction, universal Levin search and theory of compution (e.g. universal Turing machines). His book Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability, which is a highly technical and mathematical book, describes his theory of optimal Bayesian non-Markov reinforcement learning agents. Here I list other similar works.
There is also the research field called computational learning theory, which is devoted to studying the design and analysis of machine learning algorithms (from a statistical perspective, known as statistical learning theory, or algorithmic perspective, algorithmic learning theory). More precisely, the field focuses on the rigorous study and mathematical analysis of machine learning algorithms using techniques from fields such as probability theory, statistics, optimization, information theory and geometry. Several people have worked on the computational learning theory, including Michael Kearns and Vladimir Vapnik.
There is also a lot of research effort dedicated to approximations (heuristics) of combinatorial optimization and NP-complete problems, such as ant colony optimization.
There is also some work on AI-completeness, but this has not received much attention (compared to the other research areas mentioned above).