There's nothing obvious about determinism and non-determinism that leads to this. It's a bit technical.
A deterministic automaton corresponds to what we can actually build, either in hardware or in software.
A non-deterministic automaton tries all possible solutions, but to be in polynomial time it has to be able to verify a possible solution in polynomial time. If you enough of the theory, you'll recognize that an NA is equivalent to a DA with an oracle that mysteriously gives a solution, so an NA can solve something in polynomial time if a DA can verify a proposed solution in polynomial time. A nondeterministic automaton is equivalent to a deterministic automaton that tries all possible combinations, and the set of all possible combinations has exponentially more members than the set of things being combined, so if a NA can do something in polynomial time a DA can certainly do it in exponential.
NP is the set of decision problems such that a DA (hence a real computer) can verify a solution in polynomial time. If we can't verify a proposed solution in polynomial time, we certainly aren't going to be able to generate one, so NP is essentially the set of decision problems that might have real-life polynomial-time solutions.
The Traveling Salesman Problem, as usually given, isn't in NP because it's not clear how to verify that a given route is the cheapest in polynomial time. However, a variant of the TSP in which the question is whether there's a solution with a cost under X is in NP, since it's easily verifiable, and if we can solve that problem we can determine the cheapest route easily. Therefore, the TSP as usually stated is NP-hard, meaning that it's as hard to solve as an NP-complete problem.
There are problems that don't have known polynomial solutions for an NA, and problems we know aren't in NP. Those problems are usually categorized by further complexity classes (PSpace problems, for example, can be solved in polynomial space, but possibly only exponential time), or listed as undecidable. I don't know of any terms for a problem, say, that is PSpace but is not known to be in NP.