How to prove a problem is not P but NP? As I try to do some reading On P and NP, I keep finding confusing statements like the Salesman Problem cannot be solved in P, but it has solution in NP.
Is that entirely true, or is it more correct to say "There is no known solution in P"?
Furthermore, as I read papers, many times the authors prove that a problem in "NP-Hard" or "NP-Complete" for example.
Wouldn't that simply mean that they found "NP-Hard" algorithm, but there may still be a simpler solution?
Take sorting problem of a list for example. I can brute force every possible solution and check if the list is sorted, and I can claim this is NP, and show equivalency between this type of solution to some NP Class problems.
Am I thinking about this correctly?
 A: Your first point is correct, but the second isn't.
For all we know, it might be that P = NP. So when a problem is in NP, we shouldn't say about such a problem that it isn't in P. We can say it's "not known to be in P" (as you suggested) or in many cases that it's "not believed to be in P" or even (in the case of NP-hard problems) that it's "not in P unless P = NP."
Concerning the second part of your question, about NP-hardness, the first thing to notice is that there's no such ting as an "NP-hard algorithm". To say that some problem X is NP-hard doesn't say anything about actual algorithms for solving X. Rather, it means that all other NP problems Y can be reduced to X by polynomial-time reductions.  The theory of NP-completeness tells us that, in order to  verify NP-hardness of X, we don't actually have to give such reductions for all NP-problems Y; it suffices to give such a reduction for one NP-complete problem Y, for example 3-SAT. Once we've done that, we have proved that X is NP-hard, and we don't need to include any hedging like "known to be" or "believed to be" or "unless P = NP".
