Yes it is actually the infinite that is at the core of all these problems. Same with the incomputability of https://en.wikipedia.org/wiki/Kolmogorov_complexity . If you simply think in terms of bits (the finite) none of these problems exist as one can simply search all permutations.