Is machine learning successful in solving combinatorial optimisation problems in NP-hard? Discuss problem of scheduling using machine learning
You don't have to get to EXP-complete in order to get a hard problem.
NP-Complete is bad enough...

Cryptographic assumptions (e.g., the existence of one way functions) are also a good way to create hard problems

There is research in the area lead of plenty of results like Cryptographic Limitations on Learning Boolean Formulae and Finite Automata - DFA is not PAC learnable in polynomial time.

However, there is an important difference between these negative results and writing a great chess program.
The negative results means that for a given problem no algorithm will solve ALL instances (let say, in polynomial time).
That doesn't mean that you won't be able to play better the human champion on some/most/all instances.

Note that this complexity observation is indifference of the technique. Machine learning is just another (useful) way to cope with these problems.

As for machine learning ability to cope with these problems, you can find NP-Complete problems all around in machine learning (SVM, Neural Networks, Decision trees). That didn't prevent them from finding many useful models.