A neural network does not give any guarantee of solving the problem within any number of iteration. NP-hard problems can be solved, but the solution take a lot of time to find and a slightly larger problem is even harder to solve.

Neural networks is an AI method of searching the solution space in a more intelligent way than "trying everything" (true for most AI methods actually).