Good point!

There is also the case for Markov chains being theoretically able to do these if tuned well. Or even SAT problem.