Let $G$ represent an undirected graph, let $a$ and $b$ represent vertices and let $k$ represent a non-negative integer.
I have two languages:
$L_1 = \left \{ \left \langle G, a, b, k \right \rangle \mid G \text{ contains a path of at most } k \text{ from } a \text{ to } b \right \}$, and
$L_2 = \left \{ \left \langle G, a, b, k \right \rangle \mid G \text{ contains a path of at least } k \text{ from } a \text{ to } b \right \}.$
I want to show that $L_1$ is in P.
I have thought that I could show it in $\text{Satisfiability}$, but I am unsure of what I am doing: $(a \vee \lnot b )\wedge (b \vee \lnot a)\wedge(k \vee \lnot a) \wedge (k \vee \lnot b)\wedge (a \vee \lnot k) \wedge (b \vee \lnot k)$
If someone could walk me through this, that would be great, because I don't think I can use $\text{2-COL}$ to $\text{2-SAT reducibility}$ on this instance of $G$.
Secondly, I want to show that $L_2$ is NP-complete.
Now I understand that I can use the fact that $\text{Hamiltonian-Path}$ is NP-complete, but any further guidance would be gratefully appreciated.