Given: An undirected graph $G = (V, E)$ with a weight-function $d: E \rightarrow \Bbb N$.
Searching: A longest s-t-path without visiting a vertex more than once, $s, t \in V(G)$.
Can we find a solution deterministically and in polynomial time?
I already know that the Hamiltonian cycle problem is NP-complete. Now, it's easy to show that the Hamiltonian cycle problem can be reduced to the problem of finding a longest s-t-path on an undirected and unweighted graph. Therefore, it must be at least NP-hard.
But the problem of finding a longest s-t-path on an undirected and unweighted graph is simply a special case of the problem defined above, and since we know that the first one is NP-hard, the second one can't be solved deterministically and in polynomial time.
Is that correct? Or would I necessarily have to use another reduction here?
This is also NP-Hard. There are only $O(n^2)$ choices for $s$ and $t$. So if you could solve the problem you shaded in polynomial time, then by running through the only $O(n^2)$ choices for $s$ and $t$, you could find a Hamiltonian path if such a path exists, in polynomial time. i.e., if there is a Hamiltonian path, then for some choice of $s$ and $t$, that Hamiltonian path starts at $s$ and ends at $t$ (and of course the longest $s$-$t$ path is also Hamiltonian and so would be returned).
In fact, if you run through the choices of $s$ and $t$; $s$ and $t$ adjacent in $G$, you could find a Hamiltonian cycle if such a cycle exists.