Slime mould mashup models fiendish computing problem

"it becomes increasingly difficult to test a solution in polynomial time (that is, the travelling salesman problem is NP-hard)"

Hmm... I actually had to look this up, getting alzheimerish and all, but it is immediately clear that this is not a good definition.

NP-hard means that the problem is "at least as hard as" (and probably harder than) a problem in NP-complete.

How hard is that? Simples:

NP-complete problems are those problems which are easy to check if you are given a solution. "Easy to check" means there is a Turing Machine which can verify that a purported solution actually is a solution in polynomial time of the input size. This is the "P" of "NP".

However, getting a solution may be difficult. Generally you need to search through a large space, moving back and forth through it. If you have a super-parallel (exponentially large or more) Turing Machine that can run all the possible searches through the space simultaneously, and then verify each solution in polynomial time (as described above under "P") and then just print to the common tape if a correct solution was found (if it exists), then you can relax as you just need polynomial time to solve the problem overall. This is the "N" of "NP"

Actual Turing Machines do not have the luxury of being exponentially (or better) parallel, and thus reality imposes that you wait a long time (exponentially or worse) for the solution to your NP-complete problem.

Now, the NP-hard problems are even more difficult (in terms of number of operations till solution) than the ones that can be solved by the magic machine described above, so they sure are harrrd.