so a problem is in P (=poly time) if there exists a Turing machine that can solve it in polynomial time. For NP (=non-deterministic poly time) problems there exists a witness, which the Turing machine can utilize to solve the problem in polynomial time (or decide if its part of the language or not).
The question if P = NP is still unproven.
I wonder how you can prove that P is not equal to NP. My thought was that if you find a problem in NP and then prove that there is no algorithm, which can solve the problem in poly time (without witness), then P not equal NP.
So for example if you look at the Hamiltonian path problem (which is in NP) and prove that it cant be solved in poly time by a deterministic TM, then P not equal NP.
Is my thought process correct or am I missing something?
We have NP complete problems, the most known one being SAT and there are numerous others, such as hamiltonian path. If one of these problems is in P, then NP=P. If one of these isn't in P - i.e., there does not exists any poly-time TM that decides this language - then NP != P. So yes, proving P is equal or not equal to NP is equivalent to proving there does or doesn't exists an algorithm which solves one of the complete problems (such as hamiltonian path which you gave as an example).